Discrete Structures & Theory of Logic Unit 5 – Graphs & Combinatorics: AKTU previous year questions
30 AKTU questions from Unit 5 (Graphs & Combinatorics) asked in 2020–2026, tagged by marks, year and topic. In short: about 26 marks of every paper come from this unit; the most asked topic is Combinatorics & Counting (12 times); 17 questions came back in a later year. The latest ones are listed below; on the page you can filter them by 2-mark or long questions, topic and repeats.
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)
- Illustrate the following graph using an adjacency matrix: A graph with vertices V = {A, B, C, D} and edges E = {(A, B), (B, C), (C, D), (D, A)}. (2 marks, 2025, Graphs & Terminology)
- Examine whether the graphs K3 and a graph formed by adding a single vertex in the middle of one edge of K3 are homeomorphic or not. (7 marks, 2025, Isomorphism & Homeomorphism)
- Express the following (i) Euler graph and Hamiltonian graph (ii) Chromatic number of a graph (iii) Walk and path (iv) Bipartite graph (7 marks, 2025, Euler & Hamiltonian Paths)
- Prove that in any group of 13 people, at least two must have their birthdays in the same month. (7 marks, 2025, Combinatorics & Counting)
- Compare Euler circuit and Hamiltonian circuit. (2 marks, 2024, Euler & Hamiltonian Paths)
- Explain Pigeon hole principle. Describe generalized form of Pigeon hole principle. If 6 colors are to paint 37 homes. Show that at least 7 of them will be of same color. (7 marks, 2024, Combinatorics & Counting)
- Compare bipartite and complete graph with example. Draw K3,4 and K5. Explain why these two graphs are not planar. (7 marks, 2024, Isomorphism & Homeomorphism)
Most asked Unit 5 topics
- Combinatorics & Counting – asked 12 times
- Graphs & Terminology – asked 9 times
- Isomorphism & Homeomorphism – asked 5 times
Unit 5 question pattern
- 2-mark questions: 11 asked in 2020–2026
- 7-mark questions: 9 asked in 2020–2026
- 10-mark questions: 10 asked in 2020–2026
- About 26 marks from Unit 5 in every paper
- 17 questions were asked again in a later year
Unit 5 questions year by year
- 2026: 5 Unit 5 questions asked (25 marks across that year's papers)
- 2025: 4 Unit 5 questions asked (23 marks across that year's papers)
- 2024: 4 Unit 5 questions asked (23 marks across that year's papers)
- 2023: 5 Unit 5 questions asked (34 marks across that year's papers)
- 2022: 5 Unit 5 questions asked (34 marks across that year's papers)
- 2021: 1 Unit 5 question asked (10 marks across that year's papers)
- 2020: 6 Unit 5 questions asked (36 marks across that year's papers)