Results 1 to 2 of 2

Math Help - 3-Regular graph

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    3-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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    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 ?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. r-regular graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 12th 2011, 04:30 PM
  2. connectivity 3 regular graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 30th 2010, 05:27 PM
  3. k-regular simple graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 14th 2010, 05:54 AM
  4. Regular Graph
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 7th 2010, 05:35 PM
  5. 4-regular Graph
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 19th 2009, 05:49 PM

Search Tags


/mathhelpforum @mathhelpforum