Prove that a 3-regular simple graph has a 1-factor if and only if it decomposes into

copies of P4.

Prove that every 3-regular simple graph with no cut-edge decomposes into copies

of P4.

Thanks to anyone who can show me how to do this!

Printable View

- Oct 13th 2010, 07:27 PMjzellt3-Regular graph
Prove that a 3-regular simple graph has a 1-factor if and only if it decomposes into

copies of P4.

Prove that every 3-regular simple graph with no cut-edge decomposes into copies

of P4.

Thanks to anyone who can show me how to do this! - Oct 16th 2010, 04:34 AMTraveller
Solution for the first problem. Consider a perfect matching M in G. Since G is 3 regular it will decompose into disjoint non-trivial cycles if we remove M from it. Every vertex is now part of a cycle. So we can assign a separate edge to each vertex. Now we bring in M and attach such an edge to each end of each edge in M to form the required decomposition.

Now suppose there is such a decomposition in G. Notice that there will be n/2 copies of P4 in the decomposition. So there will be n endings of P4 paths in total. Since every vertex of G is odd degreed, each has to be the end vertex of at least one copy of P4 . So each vertex will be the end-vertex of exactly one copy of P4. Can you complete the proof from here ?