The expression 2^C(n,2) counts graphs only when the vertices remain distinguishable; once a question says "unlabeled", drawings that differ only because their vertices were renamed merge into one isomorphism class. For unlabeled graphs, start with the counting object and labeled formula, then enumerate n=3 directly and apply Burnside's lemma for n=4. The result for four vertices is 11, derived from 264 fixed labeled graphs across the 24 vertex permutations. The broader GATE CS exam preparation courses and test series page places this graph-counting topic within the full exam syllabus.
Fix the graph model before counting
A simple graph has no self-loops and no parallel edges. Undirected means an edge is an unordered pair {u,v}, so {u,v} and {v,u} are the same edge. In a labeled graph, the vertices stay fixed as 1,2,...,n. In an unlabeled graph, isomorphic graphs obtained by renaming vertices count once.
There are C(n,2)=n(n-1)/2 possible unordered pairs of distinct vertices. Each pair can be present or absent independently. Therefore, the number of labeled simple undirected graphs is
2^C(n,2).
For n=4, C(4,2)=4 x 3/2=6, so the labeled count is 2^6=64.
The unlabeled question is different. Those 64 labeled graphs collapse into 11 isomorphism classes, not 64/4!. If you want to strengthen the surrounding ideas of isomorphism and graph structure, use Graph Theory: Euler, Hamiltonian, Coloring for GATE CS alongside this count.
Worked example: all unlabeled graphs on three vertices
Let V={1,2,3}. The three possible edges are 12, 13, and 23. Up to renaming vertices, there are four shapes:
Graph | Edge set | Shape | Sorted degree sequence |
|---|---|---|---|
|
| Three isolated vertices |
|
|
| One edge and one isolated vertex |
|
|
| Path |
|
|
| Triangle |
|
Their edge counts are 0,1,2,3, so no two rows can be isomorphic. Their degree sequences give a second distinguishing check.
Now count the labeled realizations. G0 has one. G1 can use any one of the three possible edges, so it has three. For G2, choose which of the three vertices has degree 2, so it also has three. G3 has one.
The check is 1+3+3+1=8, and 2^C(3,2)=2^3=8. Thus there are four unlabeled graphs but eight labeled graphs on three vertices.
Why dividing by n! fails
A relabeling can leave a graph unchanged. Such a symmetry-preserving relabeling is an automorphism. Different shapes have different numbers of automorphisms, so they do not all produce the same number of distinct labeled graphs.
For n=3, G0 and K3 are preserved by all 3!=6 vertex permutations. Each therefore produces only one labeled graph. G1 is preserved when its two endpoints swap, and P3 is preserved when its two leaves swap. Each has two automorphisms, so each orbit has size 6/2=3.
That explains the unequal orbit sizes 1,3,3,1. The shortcut gives 8/3!=8/6=4/3, which cannot be a graph count. Use 2^C(n,2) for labeled graphs. For unlabeled graphs, classify isomorphism types directly when n is tiny, or use orbit counting such as Burnside's lemma.
Burnside's lemma worked completely for n=4
The 24 permutations in S4 relabel the four vertices and therefore permute the six possible edges. Suppose a vertex permutation creates c orbits among those edges. A graph fixed by that permutation must include or exclude each complete edge orbit, giving exactly 2^c fixed labeled graphs. Burnside's lemma averages these fixed-graph counts over all 24 permutations.
Vertex-permutation type | Number in | Edge orbits | Fixed graphs | Contribution |
|---|---|---|---|---|
Identity | 1 | 6 |
| 64 |
Transposition | 6 | 4 |
|
|
Double transposition | 3 | 4 |
|
|
Three-cycle | 8 | 2 |
|
|
Four-cycle | 6 | 2 |
|
|
The edge orbits for each representative permutation are as follows. For (12), they are {12}, {34}, {13,23}, and {14,24}. For (12)(34), they are {12}, {34}, {13,24}, and {14,23}. For (123), they are {12,23,13} and {14,24,34}. For (1234), they are {12,23,34,14} and {13,24}.
The exact average is
(64+96+48+32+24)/24=264/24=11.
Therefore, there are 11 unlabeled simple undirected graphs on four vertices.
Small values and a complement check
For n=1,2,3,4,5, the unlabeled counts are 1,2,4,11,34. The corresponding labeled counts are 1,2,8,64,1024, obtained from 2^C(n,2). Treat the first list as a compact check, not as evidence of an elementary power formula for unlabeled graphs.
There is another check for n=4. Group the 11 shapes by their number of edges m=0,1,2,3,4,5,6. The counts are 1,1,2,3,2,1,1, which sum to 11. Taking the complement changes m to 6-m and preserves isomorphism classes. That explains why the counts match on opposite sides of m=3.
The method in Permutations and Combinations for GATE CS: One Method can help with choosing unordered pairs and avoiding double-counting. It does not replace graph isomorphism or Burnside's lemma.
Traps that change the answer
Before calculating, ask five questions:
Are loops forbidden?
Are parallel edges forbidden?
Is the graph directed or undirected?
Are the vertices labeled or unlabeled?
Are all graphs allowed, or only connected graphs or graphs with exactly
medges?
Every answer can change the sample space. On five labeled vertices, there are C(5,2)=10 edge slots and 2^10=1024 simple undirected graphs. If exactly three edges are required, choose three of those slots: C(10,3)=120. The corresponding unlabeled exact-three-edge question requires classification by isomorphism, so 120 is not its answer.
Three errors are predictable. Using ordered pairs produces n(n-1) instead of C(n,2). Dividing by n! ignores unequal automorphism groups. Counting drawings without checking degree sequences and adjacency can merge distinct shapes or separate identical ones.
The short version and your next step
Try this speed drill. All labeled simple undirected graphs on six vertices: C(6,2)=15, so 2^15=32,768. Labeled simple undirected graphs on five vertices with exactly four edges: C(10,4)=210. Unlabeled simple undirected graphs on four vertices: 11, by classification or the Burnside calculation above.
Question stems often change one qualifier, require an exact edge count, or distinguish labeled graphs from non-isomorphic graphs. The durable method is to choose unordered edge slots, use independent presence or absence only for labeled graphs, and treat each unlabeled graph as one isomorphism class.
For broader counting foundations, continue with Engineering Mathematics for GATE Exam. For a wider GATE CS study route, use GATE Guidance by Sanchit Sir. Then redo the n=3 four-shape list without notes and reproduce the five-row n=4 Burnside table until you can explain every contribution.
