# Math Help - k-regular simple graph

1. ## k-regular simple graph

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

How would I do this?

2. 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 ?