Past exam of the computer science course of the University of Oxford / 2023 / Combinatorial optimisation / 3 / b

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$ givesThus $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)\ge 3$. ThereforeThe last inequality holds because each vertex of $S$ has vertex degree three. Furthermore,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)\ge |S|+2$, contradicting the bound $3q(S)\le 3|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 $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.

Choose a perfect matching $M$ from (i). Every vertex has exactly two incident edges in $E\setminus M$, so this spanning subgraph is a disjoint union of graph cycles. Orient each graph cycle cyclically, and let $s(v)$ be the next vertex after $v$ along its oriented graph cycle.

For each $uv\in M$, take the three-edge sequenceIts four vertices are distinct. Each $s(u)\ne u$ and $s(v)\ne v$ because the graph is a simple graph. Also $s(u)\ne v$ and $s(v)\ne u$, since $uv$ belongs to $M$, rather than $E\setminus M$. Finally $s(u)\ne s(v)$ because the successor map $s$ is a bijection on the disjoint graph cycles. Thus this is a graph path of length exactly three.

Every edge of $M$ is used once as a middle edge. Every edge of $E\setminus M$ is used once as the outgoing edge of its tail, whose unique edge of $M$ determines which graph path contains it. Hence these graph paths are pairwise edge-disjoint and cover $E$. This is the three-edge path decomposition from a perfect matching.