Cubic graph

A graph whose every vertex has degree of a vertex three.

A finite simple graph that is a cubic graph and has a perfect matching admits a partition of a set of its edges into graph paths of length three.

Proof. Delete a perfect matching $M$. The remaining spanning subgraph has vertex degree two at every vertex, so it consists of disjoint graph cycles. Orient each cyclically, giving a successor bijection $s$. Replace each $uv\in M$ by the graph path $s(u),u,v,s(v)$. The four vertices are distinct: the successor edges are not in $M$, neither is a self-loop, and injectivity of $s$ excludes $s(u)=s(v)$. Every edge of $M$ appears once in the middle, and every other edge appears once at its unique tail. Thus the graph paths cover every edge exactly once. In particular, the perfect matching theorem for a cubic graph with at most two bridges guarantees this decomposition under its hypotheses.

Every finite connected cubic graph with at most two bridges has a perfect matching.

Proof. The handshaking lemma implies that the number $n$ of vertices is an even integer. Fix a nonempty subset $S$ of the vertex set, and let $q$ count the components of $G-S$ of odd integer order. For such a component $C$, counting vertex degrees gives $3|C|=2|E(C)|+d(C)$, where $d(C)$ counts its edges to $S$. Thus $d(C)$ is a positive odd integer. If it is one, the unique outgoing edge is a bridge; this happens for at most two components. For all others $d(C)\ge 3$. Therefore $3q-4\le 3|S|$. Meanwhile $q\equiv n-|S|\equiv |S|(\mathrm{mod}2)$. If $q>|S|$, the same parity would force $q\ge |S|+2$, contradicting the preceding bound. For $S=\varnothing$ there is one component of even integer order and hence $q=0$. Apply Tutte's theorem on perfect matchings.

The bipartite cubic graph with vertices $A_i,B_i$, $i\in \mathbb{Z}/7\mathbb{Z}$, and edges $A_i{B}_i,A_i{B}_{i+1},A_i{B}_{i-2}$. The three offsets give a Tait coloring.

Triangulate a torus using the seven vertices of the complete graph $K_7$ and oriented triangles $(i,i+1,i+3)$ and $(i,i+3,i+2)$, with indices modulo seven. Every edge occurs twice with opposite orientations; each vertex has a cyclic link. The Euler characteristic is $7-21+14=0$. Its dual graph is the Heawood graph. This dual map has seven disc faces, each adjacent to all the others, so it needs seven face colors although its edges have a Tait coloring.