The number of distinct simple graphs with up to three nodes is:
A. 15
B. 10
C. 7
D. 9
GATE 1994 · Discrete Mathematics · Graph Connectivity · medium
Answer: 7 distinct non-isomorphic simple graphs with up to 3 nodes.
- Count for n=1 and n=2: n=1: 1 graph. n=2: C(2,2)=1 possible edge, 2 subsets => 2 non-isomorphic graphs. Subtotal = 3.
- Count non-isomorphic graphs for n=3: C(3,2)=3 possible edges. By edge count: 0 edges (1 class: empty), 1 edge (1 class: edge+isolated), 2 edges (1 class: path P3), 3 edges (1 class: K3). Total = 4.
- Sum all counts: Total = 1 (n=1) + 2 (n=2) + 4 (n=3) = 7. Answer: C.