Graph-counting questions look similar, but the answer changes completely when vertices are labeled rather than unlabeled, when a question asks for available edge slots rather than whole graphs, or when it fixes an edge count or a cycle length. Attempt the eight four-option questions and two answer-entry questions before opening the explanations. Use the same solving order every time: identify the object being counted, compute the available unordered vertex pairs, decide whether each pair is chosen independently, and only then apply combinations or remove isomorphic duplicates. Open the linked solved page to inspect the original question while practising.
1. Number of graphs: choose the counting model before the formula
Let M be the number of possible edges among n fixed vertices. The five counting models are maximum edge slots, labeled simple undirected graphs, labeled graphs with exactly r edges, undirected cycles of length k in K_n, and unlabeled simple graphs.
Object being counted | Count |
|---|---|
Maximum edge slots in a simple undirected graph |
|
All labeled simple undirected graphs |
|
Labeled graphs with exactly |
|
Undirected cycles of length |
|
Unlabeled simple graphs | Group labeled graphs by isomorphism; |
For four fixed labeled vertices, M=C(4,2)=6. Therefore, the number of simple undirected graphs is 2^6=64, the number with exactly two edges is C(6,2)=15, and the complete graph has six edges. Keep 6, 64, and 15 ready as checks for the first four questions.
The GATE CS Exam Preparation Courses & Test Series page is the broader catalog route when you want to place this topic inside your preparation.
2. Labeled simple graphs: edge slots, graph totals and dense graphs
Question 1: every possible edge is an independent choice
"How many simple undirected graphs, not necessarily connected, can be constructed on the fixed vertex set V = {v1, v2, ..., vn}?"
A. n(n - 1) / 2
B. 2^n
C. n!
D. 2^{n(n-1)/2}
Answer: D. There are M=n(n-1)/2 unordered pairs of distinct vertices. Each pair independently contributes an edge or no edge, so the number of labeled simple undirected graphs is 2^M=2^{n(n-1)/2}.
Question 2: maximum edges without self-loops
"The maximum number of edges in a n-node undirected graph without self loops is"
A. n^2
B. n * (n-1)/2
C. n - 1
D. (n + 1) * n/2
Answer: B. Start with n(n-1) ordered endpoint choices and divide by two because {u,v} and {v,u} represent the same undirected edge. At n=5, the maximum is 5*4/2=10; this counts edge slots, not graphs.
Question 3: maximum number of simple graphs
"Maximum number of Simple graphs possible with n vertices"
Answer-entry answer: 2^{n(n-1)/2}. Question 2 counted possible edges, but this question counts all subsets of those edges. For n=3, M=C(3,2)=3, so the labeled total is 2^3=8.
Question 4: at least a threshold number of edges
"How many graphs on n labeled vertices exist which have at least (n^2 - 3n)/2 edges?"
Answer-entry answer: sum_{k=0}^{n} C(M,k), where M=n(n-1)/2. The threshold is (n^2-3n)/2=M-n, so a qualifying graph can have at most n missing edges. Choosing k missing edges for each k=0,1,...,n gives the stated sum.
For n=4, M=6 and the threshold is 2. Direct counting gives C(6,2)+C(6,3)+C(6,4)+C(6,5)+C(6,6)=15+20+15+6+1=57. Counting at most four missing edges gives C(6,0)+C(6,1)+C(6,2)+C(6,3)+C(6,4)=1+6+15+20+15=57, confirming the answer.
3. Unlabeled simple graphs: remove relabelings that preserve the shape
Question 5: distinct simple graphs with up to three nodes
"The number of distinct simple graphs with up to three nodes is"
A. 15
B. 10
C. 7
D. 9
Answer: C. There is one shape on one node; two shapes on two nodes, with zero or one edge; and four shapes on three nodes, with zero edges, one edge, a two-edge path, or a triangle. Thus 1+2+4=7. The labeled three-node total is 2^3=8, but its three labeled one-edge graphs represent one unlabeled shape.
Continue with Graph Theory MCQs: 12 Solved Euler, Coloring, Trees for a broader mixed-topic practice set.
4. Cycle counting: choose vertices, remove rotations and reversals
Question 6: expected triangles in a random graph
"Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three?"
A. 1/8
B. 1
C. 7
D. 8
Answer: C. The graph has C(8,3)=56 vertex triples. A triple becomes a triangle only when all three required edges are present, with probability (1/2)^3=1/8, so linearity of expectation gives 56*(1/8)=7. The triangle events need not be independent for this expectation calculation.
Question 7: four-cycles in a complete labeled graph
"Let G be a complete undirected graph on 6 vertices. If vertices of G are labeled, then the number of distinct cycles of length 4 in G is equal to"
A. 15
B. 30
C. 45
D. 360
Answer: C. Choose the four participating vertices in C(6,4)=15 ways. Each four-set has (4-1)!/2=3 undirected cycles after removing rotations and the two travel directions, so the answer is 15*3=45. The independent check is P(6,4)/(4*2)=360/8=45.
If rotations and reversals still cause overcounting, revise Permutations and Combinations for GATE CS: One Method.
5. Structured graph edge counts: a 12 by 12 king-move grid
Question 8: count horizontal, vertical and diagonal edges
"Consider an undirected graph G where self-loops are not allowed. The vertex set of G is {(i, j) | 1 ≤ i ≤ 12, 1 ≤ j ≤ 12}. There is an edge between (a, b) and (c, d) if |a − c| ≤ 1 and |b − d| ≤ 1 and (a, b) ≠ (c, d). The number of edges in this graph is ______."
A. 726
B. 796
C. 506
D. 616
Answer: C. Count each orientation once: horizontal 12*11=132, vertical 12*11=132, down-right diagonal 11*11=121, and down-left diagonal 11*11=121. The total is 132+132+121+121=506.
For a second check, four corners have degree 3, forty non-corner boundary vertices have degree 5, and one hundred interior vertices have degree 8. The handshake lemma gives (4*3+40*5+100*8)/2=1012/2=506. The degree-sum method also connects naturally to Graph Theory: Euler, Hamiltonian, Coloring for GATE CS.
6. Shortest paths in arithmetic-generated directed graphs
Question 9: work backwards from 100
"Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to a vertex j if either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 is"
A. 4
B. 7
C. 23
D. 99
Answer: B. A seven-edge path is 1 -> 3 -> 9 -> 10 -> 11 -> 33 -> 99 -> 100. Reaching 100 requires first reaching 99; the fastest predecessor route to 99 uses 33, and the shortest route to 33 is 1 -> 3 -> 9 -> 10 -> 11 -> 33, already five edges. Therefore, 99 needs six edges and 100 needs seven.
Question 10: verify the shortest path with a distance recurrence
The typography and option order differ from Question 9, but the graph is unchanged. Let d(x) be the shortest distance from 1 to x. When x is divisible by 3, compare d(x-1)+1 with d(x/3)+1; otherwise, the only predecessor is x-1.
"Let 𝐺 be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex 𝑖 to a vertex 𝑗 if and only if either 𝑗=𝑖+1 or 𝑗=3𝑖. The minimum number of edges in a path in 𝐺 from vertex 1 to vertex 100 is ______ ."
A. 23
B. 99
C. 4
D. 7
Answer: D. The recurrence gives d(1)=0, d(3)=1, d(9)=2, d(10)=3, d(11)=4, d(33)=5, d(99)=6, d(100)=7. Therefore the minimum path has seven edges, which is option D in this ordering.
7. Number of graphs MCQs: trap checklist and next practice step
Trap | Recall rule |
|---|---|
Labeled vertices | Count subsets of the available edge slots |
Unlabeled vertices | Group graphs that are isomorphic |
| It counts edge slots, not graphs |
Fixed undirected cycles | Remove rotations and reversals |
Degree sum | Every undirected edge is counted twice |
Question | Type | Key |
|---|---|---|
1 | Four-option | D |
2 | Four-option | B |
3 | Answer-entry |
|
4 | Answer-entry |
|
5 | Four-option | C |
6 | Four-option | C |
7 | Four-option | C |
8 | Four-option | C |
9 | Four-option | B |
10 | Four-option | D |
On five fixed labeled vertices, calculate C(5,2), 2^10, and C(10,3) as a self-check. On five fixed labeled vertices, you should get C(5,2)=10 possible edges, 2^10=1024 simple graphs, and C(10,3)=120 graphs with exactly three edges. If any result is unclear, return to the first decision table before attempting more questions.
For sequenced practice, use GATE Guidance by Sanchit Sir. Keep asking what object is being counted before selecting a formula; that one habit prevents most graph-counting errors.
