= Three-edge path decomposition from a perfect matching
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.
\b[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.
Back to article page
