This set covers graph theory, one of the highest-weightage topics in Discrete Mathematics for GATE CS and UGC NET. It includes the handshaking lemma, degree sequences, properties of trees, Cayley's formula, Euler and Hamiltonian graphs, Euler's formula for planar graphs, chromatic numbers and bipartite graphs. Most questions can be solved with one formula and a little reasoning, which also makes the set useful for semester exams and technical interviews.
How to practise: read each question and tap the option you think is correct. You will see right away whether you got it, along with a short explanation, and your score is tracked at the bottom of the screen. This set has 18 questions.
Topics covered in this set
- Degrees and the handshaking lemma
- Trees and Cayley's formula
- Euler circuits and Euler paths
- Hamiltonian cycles
- Planar graphs and Euler's formula
- Graph colouring and chromatic polynomials
- Bipartite and complete bipartite graphs
Discrete Mathematics MCQs with answers and explanations
Q1. A simple graph has 6 vertices with degrees 3, 3, 3, 3, 4 and 4. How many edges does it have?
a) 20
b) 10
c) 12
d) 9
Q2. Which degree sequence CANNOT belong to a simple graph?
a) 2, 2, 2, 2
b) 3, 2, 2, 1
c) 3, 3, 3, 1
d) 3, 3, 2, 2
Q3. A tree has 2 vertices of degree 3, one vertex of degree 4, and every other vertex is a leaf. How many leaves does it have?
a) 5
b) 7
c) 8
d) 6
Q4. For n ≥ 3, the complete graph K_n has an Euler circuit if and only if:
a) n is odd
b) n is even
c) n is prime
d) n is a multiple of 3
Q5. A connected graph has an Euler path but no Euler circuit exactly when it has:
a) no vertex of odd degree
b) exactly one vertex of odd degree
c) exactly two vertices of odd degree
d) exactly four vertices of odd degree
Q6. A connected planar graph has 10 vertices and 15 edges. Into how many regions (faces) does any planar drawing divide the plane?
a) 5
b) 6
c) 8
d) 7
Q7. What is the maximum number of edges in a simple planar graph with 8 vertices?
a) 18
b) 24
c) 28
d) 21
Q8. Which of the following graphs is non-planar?
a) K4
b) K3,3
c) K2,5
d) the cube graph Q3
Q9. A wheel graph consists of a 5-cycle plus one hub vertex joined to all 5 cycle vertices. What is its chromatic number?
a) 3
b) 5
c) 6
d) 4
Q10. In how many ways can the vertices of a path with 4 vertices be properly coloured using at most 3 colours?
a) 24
b) 81
c) 18
d) 12
Q11. How many labelled trees (spanning trees of K5) are there on 5 labelled vertices?
a) 120
b) 125
c) 60
d) 3125
Q12. A graph is bipartite if and only if:
a) it contains no cycle of even length
b) every vertex has even degree
c) it contains no cycle of odd length
d) it is a tree
Q13. The complete bipartite graph Km,n has a Hamiltonian cycle if and only if:
a) m = n ≥ 2
b) m + n is even
c) m ≥ 2 and n ≥ 2
d) m = n + 1
Q14. A simple graph has 8 vertices and 10 edges. How many edges does its complement have?
a) 28
b) 18
c) 14
d) 54
Q15. What is the maximum number of edges in a disconnected simple graph with 7 vertices?
a) 15
b) 21
c) 20
d) 6
Q16. How many distinct Hamiltonian cycles does K6 have (ignoring the starting vertex and direction)?
a) 120
b) 60
c) 720
d) 30
Q17. How many edges does the 4-dimensional hypercube Q4 have?
a) 16
b) 64
c) 32
d) 24
Q18. Every simple planar graph contains at least one vertex of degree at most:
a) 3
b) 4
c) 6
d) 5
Quick revision notes
- Σ deg(v) = 2|E|, so the number of odd-degree vertices is even.
- A tree on n vertices has n - 1 edges; Cayley: n^(n-2) labelled trees.
- Euler circuit: connected and all degrees even; Euler path: exactly 0 or 2 odd vertices.
- Connected planar graph: v - e + f = 2; simple planar with v ≥ 3 has e ≤ 3v - 6.
- K5 and K3,3 are the smallest non-planar graphs (Kuratowski).
- A graph is bipartite iff it has no odd cycle iff its chromatic number is at most 2.
- K_n has n(n-1)/2 edges and (n-1)!/2 distinct Hamiltonian cycles.
- Hypercube Q_n has 2^n vertices and n·2^(n-1) edges.
Frequently asked questions
What is the difference between an Euler circuit and a Hamiltonian cycle?
An Euler circuit uses every edge exactly once, and a Hamiltonian cycle visits every vertex exactly once. Euler circuits have a simple degree test, but deciding whether a Hamiltonian cycle exists is NP-complete.
How do I check whether a graph is planar?
First use the necessary conditions e ≤ 3v - 6, or e ≤ 2v - 4 when there is no triangle. If they fail, the graph is non-planar. To prove non-planarity in general, find a subdivision of K5 or K3,3 (Kuratowski's theorem).
Why does every tree have at least two leaves?
A tree with n ≥ 2 vertices has degree sum 2(n - 1). If at most one vertex had degree 1, the sum would be at least 1 + 2(n - 1), which is too large, so at least two vertices are leaves.
Comments
Post a Comment