Q.1
14 Marks(a)
Define Graph, planar graph and subgraph.
(b)
Define isomorphism. Determine whether the following pair of graphs are isomorphic.
(c)
Describe Königsberg Bridge Problem with respect to graph theory.
Gujarat Technological UniversityWinter 2025 examination
GTU 3171611 Graph Theory and Combinatorics Winter 2025 Question Paper & PDF
B.E. · IT Engineering · Semester 7 · Subject code 3171611
- Total
- 70 marks
- To pass
- 23 marks (33%)
- Duration
- 2.5 Hours 10:30 AM – 1:00 PM
- Questions
- 5 with internal choice
No solutions on this paper yetNeed them for your exam? Ask once. Papers that students ask for are solved first, and we aim to add them within 24 hours.
Noted. This paper is in our queue now. Check back tomorrow.
We could not record that here. Email the paper name to hirenjsca@gmail.com and we will add it.
Q.2
14 Marks(a)
Define tree? List out the applications of tree?
(b)
What is graph coloring? Explain Greedy coloring.
(c)
Prove that the number of vertices of odd degree in a graph is always even. Also, take any graph and verify it.
OR
(c)
Prove that a simple graph with 𝑛 vertices and 𝑘 components can have most (𝑛−𝑘)(𝑛−𝑘+1) 2 edges.
Q.3
14 Marks(a)
Differentiate Permutation & Combination with proper example.
(b)
In how many different ways can you arrange the letters of the word COMPUTER taking 4 at a time?
(c)
Explain the stable matching problem.
OR
(a)
Define edge vertex connectivity and edge connectivity. Give the relation between them.
(b)
There are 9 students in a club. Three students are to be chosen to be on the entertainment committee. In how many ways can this group be chosen?
(c)
Describe Hall’s marriage theorem.
Q.4
14 Marks(a)
Explain Inclusion – Exclusion Principle.
(b)
What is Rook Polynomial? Explain expansion formula of it.
(c)
Find the length and shortest path between a and z in each of the weighted graphs Using Dijkstra’s algorithm.
OR
(a)
Write applications of Transport Network.
(b)
Give an example of following:
1)A graph that has an Eulerian circuit but no Hamiltonian Circuit
2)A graph that has a Hamiltonian circuit but no Eulerian circuit.
(c)
Explain Catalan numbers with suitable examples.
Q.5
14 Marks(a)
Define de Bruijn graph.
(b)
What is recurrence relation? Explain different types of recurrence relation.
(c)
Solving Recurrence Relation an= 7an−1−10an−2 with a0=2 and a1=3.
OR
(a)
Define Derangements.
(b)
Among 150 college students, 83 own cars, 97 own bike, 28 own motorcycles, 53 own a car and a bike, 14 own a car and a motorcycle, 7 own a bike and a motorcycle, and 2 own all three.
aHow many students do NOT own any of the three?
bHow many students own a bike and nothing else?
(c)
Solve the recurrence relation an=3an−1+2an=3an−1+2 subject to a0=1.
More Graph Theory and Combinatorics papers
Questions repeat across sessions. Working through two or three papers shows you which topics GTU asks most.
Other Semester 7 subjects
BE IT
Preparing with friends?
Send this paper to your class group. Every question has its own link.
About this paper
Official Gujarat Technological University (GTU) examination paper for Graph Theory and Combinatorics (Winter 2025, B.E. · IT Engineering, Sem 7). Features complete 70-mark regular & remedial examination pattern, official marking distribution across all 5 questions, and direct 1-click official PDF download.
Transcribed for student exam preparation from Gujarat Technological University official examination archives. Questions, syllabus guidelines, and curriculum marking schemes remain the intellectual property of Gujarat Technological University.