Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
1  
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}$. –  Jonathan Y. Aug 21 '13 at 0:56
    
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? –  StudentofEuler2718 Aug 21 '13 at 1:05
    
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 ;) –  Jonathan Y. Aug 21 '13 at 1:13

1 Answer 1

up vote 4 down vote accepted

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. :)

share|improve this answer
1  
Thank You! I was able to find more info about it here: math.ucdenver.edu/~tvis/Coursework/Graphs.pdf –  StudentofEuler2718 Aug 21 '13 at 3:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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