I have drawn the graph and the result is $6$ graphs are possible.

A simple graph can have a maximum of $\Large\binom{n}{2}$ edges and each edge can exist or not exist. Therefore,

$$\underbrace{2\times2\times2\times.......\times2}_{\binom{n}{2}\,times}\,=\,2^{\Large \binom{n}{2}}$$But this includes graphs with all possible number of edges in total.
How to solve by induction the possible number of undirected graphs that are possible with $n$ labelled nodes with $k$ edges to be present all the time.


1 Answer 1


In general for a graph with $n$ vertices, there are ${n \choose 2}$ possible edges. If you want a graph with $k$ edges, you simply choose $k$ edges from the pool of ${n \choose 2}$ possible edges.

Thus the number of labeled graphs having $n$ vertices and $k$ edges is $${{n \choose 2} \choose k}$$

In particular, for $n = 4$ and $k = 1$, you get $${{4 \choose 2} \choose 1} = {6 \choose 1} = 6$$ as you correctly found out.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .