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
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!
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 ?