Discrete Structures & Theory of Logic Unit 5 – Graphs & Combinatorics: important questions for AKTU
Unit 5 (Graphs & Combinatorics) questions that AKTU repeats most often. This unit carries about 26 marks per paper. Start with the repeated questions, then the most asked topics.
Most repeated Unit 5 questions
- If a connected planar graph G has n vertices, e edges and r region, then n – e + r = 2. (10 marks, 2021, Graphs & Terminology) – also asked in 2020, 2022, 2023, 2024
- Define planar graph. Prove that for any connected planar graph, v - e + r = 2 Where v, e, r is the number of vertices, edges, and regions of the graph respectively. (10 marks, 2020, Graphs & Terminology) – also asked in 2021, 2022, 2023, 2024
- Show that K3,3 satisfies in equality |E| ≤ 3 |V| – 6, but it is non planar.(V=No. of Vertices, E=No. of Edges, R=No. of Regions) (7 marks, 2024, Graphs & Terminology) – also asked in 2021, 2020, 2022
Most important Unit 5 topic
- Combinatorics & Counting (Unit 5: Graphs & Combinatorics) – asked 12 times in 2020, 2022, 2023, 2024, 2025, 2026
Most asked Unit 5 topics
- Combinatorics & Counting – asked 12 times
- Graphs & Terminology – asked 9 times
- Isomorphism & Homeomorphism – asked 5 times
More Unit 5 previous year questions
- Let G be a 3-regualr graph with n vertices. What is the sum of the degree of the vertices? Show that in such a graph n must be even. (7 marks, 2026, Graphs & Terminology)
- Prove that if a connected graph G is decomposed into two subgraphs g1 and g2, there must be at least one vertex common between g1 and g2. (7 marks, 2026, Isomorphism & Homeomorphism)
- Show that in any room of people who have been doing handshaking there will always be at least two people who have shaken hands the same number of times. (7 marks, 2026, Combinatorics & Counting)
- How many 4 digits number can be formed by using the digits 2,4,6,8 when the repetition of digits is allowed. (2 marks, 2026, Combinatorics & Counting)
- Draw a graph that has a Hamiltonian path not have a Hamiltonian circuit. (2 marks, 2026, Euler & Hamiltonian Paths)
Unit 5 syllabus topics
- Graphs & Terminology
- Isomorphism & Homeomorphism
- Euler & Hamiltonian Paths
- Graph Coloring
- Combinatorics & Counting