= Perfect matching theorem for a cubic graph with at most two bridges
Every finite connected <cubic graph> with at most two <bridges> has a <perfect matching>.
\b[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)\geq3$. Therefore $3q-4\leq3|S|$. Meanwhile $q\equiv n-|S|\equiv |S|\pmod2$. If $q>|S|$, the same <parity> would force $q\geq|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>.
Back to article page
