Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Given an undirected graph $G=(V,E)$. We want, if possible, to partition $G$ into paths of length 2 such that each pair of paths is edge-disjoint. I seek an algorithm with linear time $O(V+E)$ and a proof that shows us why the algorithm is correct.
My idea is that we can't partition any graph this way. But when we can, we can use DFS to partition our graph. But I can't formulate my idea.
We only need to consider the case in which the graph is connected and number of edges is even. We hence assume the above conditions once for all.
As a first observation, notice that if the graph is a star then it can easily be partitioned.
You can then show by induction that other graphs can also be partitioned. The induction is on the number $m$ of edges. If the graph has $0$ edges then the claim is trivial.
Consider an even value of $m>0$. If $G$ is a star we are done. Otherwise, since graph has at least $2$ edges, and we can compute an arbitrary rooted spanning tree $T$. Let $u$ be the deepest leaf of $T$. If there are multiple choices for $u$ prefer a vertex that has at least one incident non-tree edge. Let $v$ be $u$'s parent, and let $w$ be $v$'s parent (if any).
If $u$ has at least $2$ incident non-tree edges, then select and remove them.
Otherwise, if $u$ has exactly $1$ incident non-tree edge $e$, select and remove the path containing $e$ and $(u,v)$.
Otherwise, if $v$ has at least $1$ incident non-tree edge $e$, select and remove the path containing $e$ and $(u,v)$.
In the only remaining case neither $u$ nor $v$ have incident non-tree edges. Moreover $w$ exists, since otherwise $v$ would be the root $T$, $T$ would have height $1$, and no child of $v$ would have any incident non-tree edge, implying that $T$ is a star. Select remove the path containing $(u,v)$ and $(v,w)$.
Ignore any vertex whose degree has been reduced to $0$. The remaining graph has $m-2 \ge 0$ edges, and the claim follows by invoking the induction hypothesis.
The above proof immediately leads to a liner-time algorithm once you observe that the spanning tree of the graph needs to be computed only once.
