5
$\begingroup$

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.

enter image description here

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.

enter image description here

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hmmm . . . So all you need to do is calculate $|\text{Aut}(G)|$ and then divide that into $n!$? If so, my intuition was way off. Of course, for a graph which is not small, but which has a lot of symmetry, $|\text{Aut}(G)|$ may not be so easy to compute. $\endgroup$ – quasi Feb 9 '17 at 6:36
  • $\begingroup$ @quasi True, not easy, but if Babai's proof holds up to further scrutiny then it can be computed in quasi-polynomial time, or roughly $n^{f(n)}$ where $f(n) = O(\log^k n)$ for some $k$. $\endgroup$ – Erick Wong Feb 9 '17 at 6:43
  • $\begingroup$ @quasi See also Brendan McKay's famous nauty program: pallini.di.uniroma1.it. $\endgroup$ – Erick Wong Feb 9 '17 at 6:47
  • $\begingroup$ :Thanks for the nice explanation, and for the references. $\endgroup$ – quasi Feb 9 '17 at 6:56
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This boils down to computing the automorphism group of $G$, which while non-trivial, is a very well-studied problem (recently Babai has announced a significant advance in this area: people.cs.uchicago.edu/~laci/update.html). $\endgroup$ – Erick Wong Feb 9 '17 at 6:37
  • 1
    $\begingroup$ I didn't see the connection to the automorphism group, but now I see it. Still, my answer survives partially intact in the sense that for each graph type, a separate analysis would need to be made to determine the size of the automorphism group. Also, if Bonnaduck finds the problem interesting, I think my suggestion to explore special cases would be both more fun and ultimately more rewarding than just looking up what's currently known. $\endgroup$ – quasi Feb 9 '17 at 6:49
  • $\begingroup$ @quasi I ultimately was trying to use this to solve a something else, so delving in to this problem was not entirely the goal. But nonetheless, I completely agree with you, personal research outweighs an internet search. $\endgroup$ – Bonnaduck Feb 10 '17 at 16:38
  • $\begingroup$ @Bonnaduck: Well, with all those pictures you posted, it did look like you were trying to explore the problem, so I felt that continuing that process would be a valuable learning experience. But if it's only the answer that counts, the formula in Erick Wong's answer is what you want. However, for a given graph $G$, if you want to actually use that formula, then you need some method to compute $|\text{Aut}(G)|$. That computation can be done easily for small graphs $G$, or for graphs $G$ with not a lot of symmetry, but otherwise, while doable, it's a nontrivial task. $\endgroup$ – quasi Feb 10 '17 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.