How many 1-regular graphs can be produced by deleting edges from a even complete graph?

289 Views Asked by At

Given a complete graph $K_n$ where $n > 1$ and $n$ is even, how many distinct 1-regular graphs can be produced by only deleting edges?

By "distinct" I mean the vertices are numbered or taken based on the adjacency matrix.

1

There are 1 best solutions below

5
On BEST ANSWER

Suggestion: For $n$ even: Say the vertices are $v_1,v_2,\dots,v_n$.

Pick a vertex to be joined to $v_1$ by an edge.

Find the lowest numbered unused vertex, and pick a different unused vertex to be joined by an edge.

Etc.

The correct anaswer is $\frac{n!}{(2^{\frac{n}{2}}) (\frac{n}{2})!}$