Let $G$ be a graph on $n$ vertices and $m$ edges. How many copies of $G$ are there in the complete graph $K_n$?
For example, if we have $C_4$, there are $3$ subgraphs of $C_4$ in $K_4$, as seen below.
However, if we have a different graph $G$ with the same amount of edges and vertices as $C_4$, we may get a different number of subgraphs, as seen below.
Is there a general formula for this? I feel like I've read about this before (maybe on Wolfram), but the problem's name escapes me.
Best Answer
This is a very simple instance of orbit-stabilizer: every permutation of the $n$ vertices induces an embedding of $G$ in $K_n$, but two permutations result in the same subgraph iff they differ by an automorphism of $G$. Thus the number of distinct subgraphs is just $n!/|\text{Aut}(G)|$.
For the second case, $|\text{Aut}(G)| = 2$ because you can swap the two vertices of degree $2$. For the $4$-cycle case, $\text{Aut}(C_4)$ is the dihedral group on $4$ points, which has order $8$. This correctly predicts the observed $12$ and $3$ subgraphs, respectively.