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

How would I do this?

Printable View

- Oct 13th 2010, 07: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, 04: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 $\displaystyle v_1, v_2, ... v_{k+1}$, delete the edges $\displaystyle (v_1, v_2), ( v_3, v_4), ..., (v_{k-2}, v_{k-1})$.

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

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

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

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