GATE CS 1994 Q1.6 — Graphs: Connectivity, Matching, Colouring

To find the number of distinct simple graphs with up to three nodes, we consider the isomorphism classes (unlabeled graphs) for $n = 1, 2,$ and $3$ vertices.

Let $n$ be the number of vertices in the graph:

1. For $n = 1$ vertex:
   • There is only $1$ possible graph: a single isolated vertex.
2. For $n = 2$ vertices:
   • $0$ edges: Two isolated vertices.
   • $1$ edge: A single edge connecting the two vertices ($K_2$).
   • Total for $n = 2$ is $2$ graphs.
3. For $n = 3$ vertices:
   • $0$ edges: Three isolated vertices.
   • $1$ edge: One edge and one isolated vertex.
   • $2$ edges: A path of length 2 ($P_3$).
   • $3$ edges: A triangle ($K_3$ or $C_3$).
   • Total for $n = 3$ is $4$ graphs.

Summing these up, the total number of distinct simple graphs with up to three nodes is:

Hence, the correct option is C.