How many subgraphs of $G$ are there in $K_n$? 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.
 A: 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.
A: I could be wrong, but unless $G$ has a very simple structure, I would not expect there to be a known formula for the number of distinct subgraphs of $K_n$ that are isomorphic to $G$.

My sense is that the best you could hope for is to be able to answer the question for special cases, and even then, such cases will typically need reasoning customized for the special case.

If the problem interests you, rather than asking for answers, continue to explore it, without even bothering to do an internet search.

For example, to get started, try the problem for the case where:


*

*$G$ is a path of length $k$.

*$G$ is a cycle of length $k$.

*$G$ has $k$ vertices, all of degree $0$.

*$G$ has $k$ vertices, all of degree $1$.

*$G$ has $k$ vertices, all of degree $2$.

*$G$ is connected, with one vertex of degree $k \ge 3$, and all other vertices of degree $1$.

*$G$ is a binary tree such that, all leaf nodes have distance $k$ from the root. Clearly, if $k$ is too big, there won't be any such subgraphs of $K_n$. How big can $k$ be?


Some of the above will be easy; some less so.
