= Solution
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> sequence
$$
s(u),\ u,\ v,\ s(v).
$$
Its 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>.
\Image[/past-exam-of-the-computer-science-course-of-the-university-of-oxford/2023/combinatorial-optimisation-path-decomposition.png]
{title=On a triangular prism, orient the two remaining <graph cycles> and extend each <perfect matching> <edge> by its endpoints' outgoing <edges>; the three colors partition all nine <edges> into length-three <graph paths>}
Back to article page
