GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 3

Question

The number of possible connected simple graphs with $3$ labelled vertices is ________

Comments

@gatecse Hi sir can we do it like this. Between n vertices we can have n(n-1)/2 edges so for 3 we can have max 3 edges. For a connected graph of 3 vertices we should include atleast 2 edges so we can say that we can form  connected by choosing 2 or 3 out of edges. 3c2+3c3= 3+1= 4.

Here no cycle will be formed in disconnected graph beacuse atleast 3 edges are required for it.

---

Yes, that's valid.

Answer 1

There are $\binom{n}{2}=\frac{n(n-1)}{2}$ pairs of distinct points to be connected to form an edge. If self loops and multiple edges between two vertices are not allowed , each of these pair determines one possible edge, and any subset of those possible edges for a distinct graph (the vertex set is fixed here and only by changing the edge set we form a distinct graph as $G=(V,E)$. A set with $\binom{n}{2}$ elements has $2^{\binom{n}{2}}$ subsets, so there are $2^{\binom{n}{2}}$ possible simple graphs.

$\therefore$ The number of possible simple graphs with $3$ labelled vertices $=2^{\frac{3\cdot2}{2}} = 2^{3} = 8$.

Now, this also includes disconnected graphs. There is no closed form solution to find the number of connected graphs with $n$ labelled vertices. But we can easily enumerate this for $n=3$ as follows.

$\{\{a-b, b-c\}, \{a-c, b-c\}, \{a-b, a-c\}, \{a-b, b-c, a-c\}\}$

So, the correct answer is $4.$