1
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

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.