I have been studying a little graph theory on my own and a simple google search has not helped so I am deciding to turn to math stack exchange.

My question is: Given a complete graph $K_{n}$ where $n\ge 2$, how many non-isomorphic subgraphs occupy it?

My initial thought was that the formula was going to involve powers of 2 since at first glance it seems as we are counting subsets. Hence the power set formula, Given a set A with $\alpha$ elements there exists $2^\alpha$ subsets of set A.

So I took a look at a couple of cases.

For $K_{2}$, there are 2 non-isomorphic subgraphs: An edge connecting the two vertices and a set of two vertices not connected by an edge. So I thought to myself: "Ok the formula is $2^{n-1}$ since I was able to deduce on my own earlier that a complete graph on $n$ vertices $K_{n}$ has $\frac{n\cdot(n-1)}{2}$ -or the summation of the other $n-1$ vertices. So I thought, maybe for $K_{n}$ we are counting in a similar fashion since our lower bound is at $n\ge2$.

For $K_{3}$ I found that there were 4 non-isomorphic sugraphs. $2^{3-1} = 4 $So far so good.

Next $K_{4}$, if my hypothesis was correct I would have 8 non-isomorphic subgraphs. Turns out I was only able to find 12.

Looking back we might see that the number of non isomorphic subgraphs might be more reated to the number of edges rather than the number of vertices on the graph. However for $K_{4}$ with 6 edges this would lead to $2^{6-1}=32$ edges which is an overcount.

Can someone give me a lax proof of what the actual formula is?

For example the pattern that I noticed with the number of edges on a complete graph can be described as follows:

Given a complete graph $K_{n}$ with vertices $\{X_{1},X_{2}, X_{3},\ldots,X_{n}\}$ we may arrange the vertices as a locus around an imaginary center point and form $n$ edges to form a regular $n$-gon. We then begin to connect the rest of the vertices in a circular manner.

Since $X_{i}$ has already formed two edges there are $n-3$ edges going from $X_{i}$. Next adjacent to $X_{i}$ the vertice $X_{i+1}$ has not been affected by the new edges formed in the last step so there are another $n-3$ edges made. The next vertice $X_{i+3}$ however has had an edge drawn from $X_{i}$ two steps ago so there are $n-3$ new edges formed. This process continues until we get to $X_{i+(n-2)}$.

When simply put, the steps to make this complete graph leaves us with the following sum of edges:

$n + (n-3) + (n-3) + \ldots + 1$ = $n + (n-3) + \frac{(n-2)\cdot(n-3)}{2}$ = $n + \frac{2(n-3)+(n-2)\cdot(n-3) }{2}$ = $n + \frac{(n)\cdot(n-3)}{2}$ = $\frac{2n+(n)\cdot(n-3)}{2}$ = $\frac{n(n-1)}{2}$.

Therefore a complete graph $K_{n}$ on $n$ vertices has $\frac{n(n-1)}{2}$ edges.

An explanation of that sort would be lovely. Thanks!

  • 1
    $\begingroup$ You could actually count the edges of complete graphs more easily. Since there are $n$ vertices, each of them connected to $n-1$ edges, and every edge connecting exactly two vertices (hence counted twice), the total number of edges is $\frac{n(n-1)}{2}$. $\endgroup$ – Jonathan Y. Aug 21 '13 at 0:56
  • $\begingroup$ That is another more efficient way of proving the number of edges in a complete graph, but the question still remains: how many non-isomorphic subgraphs are in a complete graph? $\endgroup$ – StudentofEuler2718 Aug 21 '13 at 1:05
  • $\begingroup$ Yes, I understand. I'm thinking of getting it as a recurrence relation, but chances are someone who already knows the answer will come along before I'm done ;) $\endgroup$ – Jonathan Y. Aug 21 '13 at 1:13

There's a fair amount of information at https://oeis.org/A000088: "Number of graphs on $n$ unlabeled nodes". The classic reference seems to be Harary and Palmer's book Graphical Enumeration.

As you've seen, $K_n$ has $\frac{n(n-1)}{2}=\binom{n}{2}$ edges. There are $2^\binom{n}{2}$ ways to select a subset of these edges. If "most" of the resulting subgraphs don't have much symmetry, then you'd expect this formula to overcount the number of non-isomorphic graphs by a factor of $n!$. It turns out that this is asymptotically true! But don't ask me to prove it. :)


You need to consider two thinks, the first number of edges in a graph not addressed is given by this equation Combination(n,2) becuase you must combine all the nodes in couples, In addition you need two thing in the possibility to have addressed graphs, in this case the number of edges is given by the Permutation(n,2) because in this case the order is important.

the second the number of sub graphs from a graph is given by the equation power(2,n), this is the power set of a especific set in this case a graph with n nodes(elements or items in any other set)

I advice you to study some of math discrete before going to graphs

All the best

  • $\begingroup$ I don't think this really answers the question. The OP is, at least implicitly, looking for non-isomorphic subgraphs. $\endgroup$ – pjs36 May 18 '16 at 18:46

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.