Results 1 to 2 of 2

Math Help - k-regular simple graph

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    k-regular simple graph

    For each k > 1 construct a k-regular simple graph having no 1-factor.

    How would I do this?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    If k is even consider the clique with k+1 vertices, if k is odd then do the following:

    1) In a k+1 clique where the vertices are v_1, v_2, ... v_{k+1}, delete the edges (v_1, v_2),  ( v_3, v_4), ...,   (v_{k-2}, v_{k-1}).

    2) Insert a new vertex v'_1 and join it to v_1, ...., v_{k-1}.

    3) Do this to k different such cliques and create corresponding v'_1, ..., v'_k.

    4) Introduce a vertex v" and join it to v'_1, ..., v'_k.

    Can you see why this graph will not have a perfect matching ?
    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. 3-Regular graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 16th 2010, 05:34 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