Properties of graphs and trivalent graphs

GRAPHS

A graph is the action of a bilateral, reciprocal relationship (example: friendship) on the members of a set (example: the characters in Jane Austen's novels.) Clearly, there is no natural drawing of a graph. Nonetheless, we can always contrive a drawing by arbitrarily assigning to each member of the set a distinct point in space, its node, and then drawing curved or straight lines, edges, between nodes whose corresponding set members are joined by the relationship.

The valence of a node is the number of edges that join to it. The valence of an edge—i.e, the number of vertices that are joined by it—is always 2. A graph is n-valent if all of its nodes have valence n.

We allow multiple instances of the relationship to exist between the same two members (parallel edges); and we also allow instances of the bilateral relationship to exist where both parties are the same individual (a self-loop.) (Note that the existence of either of these these situations will require us to use curved lines in drawing the graph.) A graph having neither parallel edges nor self-loops is called a simple graph. There is such an abundance of non-intersecting lines in 3-space that every simple graph can be drawn using straight lines intersecting only at the nodes. Curved lines allow all graphs to be drawn in 3-space. Graphs that can be drawn in 2-space using curved, non-crossing lines are called planar. 

In outline form, the hierarchy of graph classes is:

graphs (historically, pseudographs)

     multigraphs = graphs without self-loops

          simple graphs = graphs with neither self-loops nor parallel edges (historically, graphs)


A walk in a graph is an alternating sequence of nodes and edges such that successive pairs of nodes are indeed joined in the graph by the edge named between them. A walk can re-travel the same edge or pass through the same node any number of times. A trail is a walk where no edge is re-travelled. A trail where furthermore, no node is passed through more than once, is called a path. A cycle is a closed path (the node where a cycle both begins and ends is not considered to be passed through more than once.) A cleaner definition of a cycle is a connected 2-regular graph—see terms defined below. The length of a cycle is the positive integer that gives the number of edges in it—there is no such thing as a 0-length cycle. A cycle is termed odd or even as its length is odd or even. A graph with no odd cycles is called bipartite. In a bipartite graph the nodes can be properly bicolored, e.g. each node can be colored black or white such that no two nodes of the same color are joined by an edge. The length of the shortest cycle in a graph is its girth.

A graph is not necessarily all in one connected piece. The smallest number of walks that can span the graph (i.e., include every node) is k, the 0th Betti number, the number of components of the graph. A graph with k = 1 is termed connected.

A graph with no cycles is called a forest. A single component of a forest (i.e., a connected, acyclic graph) is called a tree. An edge that is not part of any cycle is called a bridge. Thus every edge in a forest is a bridge, and—having indeed no odd cycles—every forest is bipartite.

The minimum number of edges whose deletion reduces a graph to a forest is o, the cyclomatic number, or 1st Betti number of the graph.

o = m − n + k,

where, n is the number of nodes and m the number of edges.

The minimum number of edges whose deletion disconnects a graph is its edge connectivity. For example, the edge connectivity of a multicomponent graph is 0, while the edge connectivity of a connected graph containing a bridge is 1.

The minimum number of nodes whose deletion disconnects a graph is its vertex connectivity, or simply its connectivity.

Edge connectivity and vertex connectivity are rather different things. For example, a good strategy for edge-disconnecting a network of friends would be to break a friendship of a person with few friends in the network. In contrast, a good strategy for vertex-disconnecting a network of friends would be to remove from the network someone with many friends in the network.

A tree that spans a graph (includes every node) is called a spanning tree—a spanning tree is a connected, acyclic subgraph that spans the graph. Every component has a spanning tree.

A closed trail (no edges are re-travelled) that includes every edge in a graph is called an Eulerian circuit. If such a closed trail exists, the graph is termed Eulerian. A necessary and sufficient condition for a graph to be Eulerian is that the valence of every node is even.

A 1-factor, or perfect matching, is a 1-valent subgraph (i.e., a set of disjoint edges) that spans the graph.

A 2-factor is a 2-valent subgraph (i.e., a set of disjoint cycles) that spans the graph. If there exists a single-component 2-factor, the graph is termed Hamiltonian.

A graph is termed n-regular or n-valent (or zero-valent, monovalent, bivalent, triavalent, etc.) if every vertex has valence n.




TRIVALENT (3-REGULAR OR CUBIC) GRAPHS

A graph where the valence of every node is 3 (every node is the junction of three edges) is called 3-regular, trivalent, or cubic.

A zero-valent graph, or empty graph, is simply an unconnected set of nodes. A monovalent graph is a collection of disconnected line segments. A bivalent graph is composed of disconnected cycles. But, a trivalent graph may have great complexity. As we will see, any sort of graph, and all its embedding in two dimensional surfaces, can be studied in the guise of edge-colored trivalent graphs.

Every cubic graph has an even number of nodes. In particular, for any cubic graph there is an integer, h, such that n = 2h and m = 3h.

Every cubic graph is cyclic.

A cubic graph having a self-loop also has a bridge.

In a cubic graph with n>2, no edge can have more than one parallel.

In every cubic graph, edge connectivity is numerically equal to vertex connectivity.

The number of Hamiltonian cycles in a cubic graph is even.

If one Hamiltonian cycle passes through a given edge of a cubic graph, another Hamilton cycle passes through the same edge.

Nearly all cubic graphs are Hamiltonian  (i.e., the likelihood that a randomly chosen cubic graph will be Hamiltonian goes to 1 as n goes to infinity.)