Every finite connected cubic graph with at most two bridges has a perfect matching.
Proof. The handshaking lemma implies that the number of vertices is an even integer. Fix a nonempty subset of the vertex set, and let count the components of of odd integer order. For such a component , counting vertex degrees gives , where counts its edges to . Thus 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 . Therefore . Meanwhile . If , the same parity would force , contradicting the preceding bound. For there is one component of even integer order and hence . Apply Tutte's theorem on perfect matchings.

Articles by others on the same topic (0)

There are currently no matching articles.