Subgraphs of Complete graphs 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!
 A: 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. :)
A: 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
A: The number of subgraphs (including the isomorphic subgraphs and the disconected subgraphs) of a comple graph (with n>=3) is 
$$      \sum_{k=1}^n   {n \choose k}  ( 2^{k \choose 2} )          $$
I found it in Grimaldi, R. P. (2003) Discrete and Combinatorial Mathematics. (5th ed.) Pearson. Chap. 11. Solutions book.
I'm trying to proove it.
Cheers, 
