Questions about the complete graph

170 Views Asked by At

How many edges has the complete graph $K_n$ ? How many subgraphs has $K_n$?

A complete graph has $\binom{n}{2}= \frac{n \cdot (n-1)}{2}$ edges.Is this correct? And what's about the second question?

1

There are 1 best solutions below

0
On

The number of edges you suggest is correct:Equal to all the possible ways to pick 2 points out of $n$. Regarding your second question, the number of all subgraphs is:

$$\Sigma_{k=0}^n \binom{n}{k} 2^{\binom{k}{2}}$$

Briefly the above formula means: First choose $k$ points out of $n$. For the associated set of $\binom{k}{2}$ edges there are $2^{\binom{k}{2}}$ ways to include or not each one of them in the subgraph.