Finite, infinite, null, trivial and complete graphs can look like a short definition list. In questions, however, those definitions quickly become edge counts, spanning-tree deletions, cliques and mixed-property checks. The challenge is choosing and combining the correct counting rule, so attempt each question before reading its explanation. Questions 2, 4, 6, 9, 11 and 12 continue through the Types of Graphs practice hub, while GATE CS Exam Preparation gives the wider syllabus route.
Types of graphs: the definition and formula card to use before the MCQs
A finite graph has finite vertex and edge sets. An infinite graph has an infinite vertex set, edge set, or both. A null graph on n vertices has no edges, while a trivial graph has exactly one vertex and therefore no edges. In a simple complete graph K_n, every unordered pair of distinct vertices is adjacent. Thus |E(K_n)| = n(n-1)/2, and every vertex has degree n-1.
Calibrate those definitions at n = 6. The null graph N_6 has 6 vertices, 0 edges and degree sequence (0,0,0,0,0,0). The trivial graph K_1 has 1 vertex and 0 edges. For the complete graph, |E(K_6)| = 6 x 5 / 2 = 15, its degree sequence is (5,5,5,5,5,5), and its degree sum is 6 x 5 = 30 = 2 x 15.
An infinite path gives an important contrast: take vertex set Z and edges {i,i+1} for every integer i. The graph is infinite, yet every vertex has finite degree 2. For neighbouring ideas, revise Graph Theory: Euler, Hamiltonian, Coloring for GATE CS.
Result | Formula or test |
|---|---|
Edges in |
|
Edges in a spanning tree |
|
Labelled spanning trees of |
|
Clique | A complete subgraph |
Self-complementary edge count |
|
4-cycles in |
|
Complete graph MCQs 1-3: definition and maximum edge count
Question 1
GATE 2002, Computer Science
The maximum number of edges in an n-node undirected graph without self-loops is:
A. n²
B. n(n - 1)/2
C. n - 1
D. n(n + 1)/2
Correct answer: B. n(n - 1)/2.
An edge in a simple undirected graph is an unordered pair of distinct vertices. There are C(n,2) = n(n-1)/2 such pairs, and taking every pair produces K_n; self-loops would alter the count but are explicitly excluded.
Question 2
CoCubes 2023, Computer Science
If every node in a graph is connected to every other node, then the graph is called:
A. Complete graph
B. Subgraph
C. Sparse graph
D. None of the above
Correct answer: A. Complete graph.
Every distinct pair of vertices is adjacent, which is precisely the definition of a complete graph. A subgraph describes containment, while a sparse graph has relatively few edges.
Question 3
Indian Space Research Organization 2013, Computer Science
The number of edges in an n-vertex complete graph is?
A. n * (n-1) / 2
B. n * (n+1) / 2
C. n2
D. n * (n+1)
Correct answer: A. n * (n-1) / 2.
Each of the n vertices is adjacent to n-1 others, giving degree sum n(n-1). The handshaking lemma counts each edge twice, so division by 2 gives n(n-1)/2.
Types of graphs MCQs 4-6: loops, spanning trees and round-robin graphs
Question 4
TPSC 2025, Computer Science
In a graph, if there is a loop at a vertex, then it is called
A. Simple graph
B. Multigraph
C. Complete graph
D. Tree
Correct answer: B. Multigraph, following the terminology this question uses.
A simple graph excludes loops and parallel edges, so option A cannot fit. Many exam texts classify a graph with a loop as a multigraph, while stricter graph-theory texts use pseudograph when loops are allowed. Among the listed options, B matches the intended convention.
Question 5
UPLT 2018, Computer Science
From a complete graph by removing maximum ______ edges, we can construct a spanning tree.
A. e - n + 1
B. n - e + 1
C. n + e - 1
D. e - n - 1
Correct answer: A. e - n + 1.
Start with the connected complete graph containing e edges. A spanning tree on the same n vertices retains exactly n-1 edges, so the maximum removable count is e - (n-1) = e - n + 1.
Question 6
Infosys 2023
A set of football matches is organized in a round-robin fashion, i.e., every team plays against every other team once. If 21 matches are played in total, how many teams participated?
A. 8
B. 7
C. 9
D. None of these
Correct answer: B. 7.
Represent every team by a vertex and every match by an edge, giving K_n. Solve n(n-1)/2 = 21, so n(n-1) = 42; because 7 x 6 = 42, seven teams participated.
Complete graph MCQs 7-9: spanning-tree counts and clique size
Question 7
RPSC 2024, Computer Science
What are the maximum number of spanning trees (Tₙ) possible for a complete graph K₅ on 5 vertices?
A. 100
B. 20
C. 200
D. 125
Correct answer: D. 125.
Cayley's formula says that a labelled complete graph K_n has n^(n-2) spanning trees. Therefore T_5 = 5^(5-2) = 5^3 = 125, so D is correct.
Question 8
UGC NET 2019, Computer Science
A clique in an undirected graph S = ⟨V, E⟩ is a subset V′ ⊆ V of vertices, such that
A. If (u, v) ∈ E then u ∈ V′ and v ∈ V′
B. If (u, v) ∈ E then u ∈ V′ or v ∈ V′
C. Each pair of vertices in V′ is connected by an edge
D. All pairs of vertices in V′ are not connected by an edge
Correct answer: C. Each pair of vertices in V' is connected by an edge.
A clique is a vertex subset whose induced subgraph is complete, so every pair of vertices in V' must be adjacent. Options A and B constrain endpoints of edges in the whole graph instead of requiring all pairs inside the chosen subset.
Question 9
Consider the collection of all simple undirected graphs with 10 vertices and 6 edges. The number of vertices in the largest complete subgraph (clique) is __________.
Options: none; this is a numerical-answer question.
Correct answer: 4.
A clique on r vertices consumes C(r,2) edges. Six edges make K_4 because C(4,2) = 6, but K_5 would require C(5,2) = 10; the other six vertices may be isolated, so the maximum clique size is 4.
Types of graphs MCQs 10-12: maximal cliques, mixed properties and 4-cycles
Question 10
UGC NET 2016, Computer Science
A clique in a simple undirected graph is a complete subgraph that is not contained in any larger complete subgraph. How many cliques are there in the graph shown below ?
A. 2
B. 4
C. 5
D. 6
Correct answer: C. 5.
The four maximal triangles on the left are {a,b,g}, {a,d,g}, {b,e,g} and {d,e,g}. The vertices {b,c,e,f} form one K_4; its internal triangles are not separate maximal cliques because each lies inside that larger complete subgraph, giving 4 + 1 = 5.
Question 11
Which of the following are true?
A. K₅₀ is the Euler graph
B. Even cycles are bipartite
C. Edges in a n-cube graph is n2ⁿ⁻¹
D. A graph with 10 vertices can never be self-complementary
Correct answer: B, C and D.
Check the statements separately. K_50 has degree 49 at every vertex, so it is not Eulerian; every even cycle is 2-colourable; and C is intended as n x 2^(n-1), obtained from 2^n vertices of degree n and the handshaking lemma. A self-complementary graph on 10 vertices would require 10 x 9 / 4 = 22.5 edges, which is impossible.
Question 12
Number of cycles of length 4 that are possible in the complete bipartite graph k₄,₆ is ____.
Options: none; this is a numerical-answer question.
Correct answer: 90.
Every 4-cycle in K_{4,6} chooses two vertices from each part, and each such selection determines one cycle. Hence the number is C(4,2) x C(6,2) = 6 x 15 = 90.
Types of graphs answer traps: how to check the set without memorising labels
Trap | Check | Example from this set |
|---|---|---|
Treating null and trivial as synonyms | Count vertices as well as edges |
|
Forgetting division by 2 in | Count unordered pairs or halve the degree sum |
|
Counting cliques that are not maximal | Test whether a larger complete subgraph contains them | Triangles inside the Question 10 |
Using | Use it only when the graph is a tree | A spanning tree retains |
Reading MSQ as single-choice | Check every statement independently | Question 11 has three correct choices |
Use a 30-second audit: translate the property into adjacency or degree language, count unordered vertex pairs, apply n-1 only after identifying a tree, and test whether a required edge count is integral. Without looking back, re-derive K_6 -> 15, round robin 21 -> 7, K_5 -> 125, and K_{4,6} -> 90. Then use Graph Theory MCQs: 12 Solved Euler, Coloring, Trees for adjacent practice.
Types of graphs MCQs: the short version and next step
Null means zero edges, trivial means one vertex, and complete means every distinct pair is adjacent. Keep |E(K_n)| = n(n-1)/2, n-1 edges in a tree, and the definition of a clique as complete on its chosen vertices. A graph can still be infinite when every individual vertex has finite degree.
Use Questions 1-6 to practise definition-to-count translation. Use Questions 7-10 to practise spanning trees and cliques in complete graphs, and Questions 11-12 to practise mixed properties and counting. If you want the complete Graph Theory lesson sequence and practice route, use GATE Guidance by Sanchit Sir. If only this definition family is weak, redo these 12 questions from a blank page before moving on.
