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 ?