= Solution
Use <Tutte's theorem on perfect matchings>: a finite <graph> has a <perfect matching> if and only if, for every $S\subseteq V$, the number $q(S)$ of <connected components of a graph> of <odd integer> order in $G-S$ is at most $|S|$.
First, the <handshaking lemma> gives $3|V|=2|E|$, so $|V|$ is an <even integer>. Fix $S\ne\varnothing$. For each <connected component of a graph> $C$ of <odd integer> order in $G-S$, let $d(C)$ count its <edges> to $S$. Counting <vertex degrees> inside $C$ gives
$$
3|C|=2|E(C)|+d(C).
$$
Thus $d(C)$ is an <odd integer>; it is positive because $G$ is a <connected graph>. If $d(C)=1$, its unique outgoing <edge> is a <bridge>. Distinct such components yield distinct <bridges>, so there are at most two of them. Every other such component has $d(C)\geq3$. Therefore
$$
3q(S)-4\leq\sum_{C:\,|C|\text{ odd}}d(C)\leq3|S|.
$$
The last inequality holds because each <vertex> of $S$ has <vertex degree> three. Furthermore,
$$
q(S)\equiv |V\setminus S|\equiv |S|\pmod2,
$$
since components of <even integer> order do not affect <parity>, and $|V|$ is an <even integer>. If $q(S)>|S|$, this <parity> forces $q(S)\geq|S|+2$, contradicting the bound $3q(S)\leq3|S|+4$.
For $S=\varnothing$, the only component is the whole <connected graph>, of <even integer> order, so $q(\varnothing)=0$. Thus every $S$ satisfies the criterion, and \b[$G$ has a <perfect matching>]. This proves the <perfect matching theorem for a cubic graph with at most two bridges> directly from <Tutte's theorem on perfect matchings>.
Back to article page
