Sizes of graph classes

Consider the set of vertices \(\{1{,}2,…,n\}\). On this set, determine the number of distinct (but mutually isomorphic):

Variant
Complete graphs \(K_n\).
Answer
There is only one complete graph on the given set.
Variant
Paths \(P_n\).
Solution
We can write the same path in two distinct ways as a sequence of consecutive vertices.
Answer
There are \(\frac{n!}2\) distinct paths.
Variant
Cycles \(C_n\).
Solution
We can describe the same cycle in \(2n\) distinct ways as a sequence of consecutive vertices.
Answer
There are \(\frac{(n-1)!}2\) cycles.
Variant
Complete bipartite graphs \(K_{k,n-k}\) depending on \(k\).
Solution
If \(k\ne \frac{n}{2}\), then every choice of a \(k\)-element subset uniquely determines a bipartite subgraph. Otherwise we may obtain the same graph by choosing an \(k\)-element subset or its complement.
Answer
The number of complete bipartite graphs is \(\binom{n}{k}\) for \(n\ne 2k\), otherwise \(\frac12\binom{n}{k}\).
Variant
Disjoint unions of two complete graphs \(K_k\cup K_{n-k}\) depending on \(k\).
Solution
Because the complements of the graphs we seek are complete bipartite, the answer will be the same as in the preceding variant.
Answer
There are \(\binom{n}{k}\) such graphs for \(n\ne 2k\), otherwise \(\frac12\binom{n}{k}\).
Variant
Graphs in which every vertex has degree 1.
Solution
These graphs are called matchings and there are as many of them as there are ways to divide the set of vertices into pairs.
Answer
If \(n\) is odd then the graph has no matchings. Otherwise there are \(\binom{n}{2{,}2,…,2}\frac1{(n/2)!}=\frac{n!}{2^{n/2}(n/2)!}\) of them.