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

How would I do this?

Printable View

- Oct 13th 2010, 08:26 PMjzelltk-regular simple graph
For each k > 1 construct a k-regular simple graph having no 1-factor.

How would I do this? - Oct 14th 2010, 05:54 AMTraveller
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 , delete the edges .

2) Insert a new vertex and join it to .

3) Do this to k different such cliques and create corresponding .

4) Introduce a vertex v" and join it to .

Can you see why this graph will not have a perfect matching ?