Question 1
(a)
Define Graph, planar graph and subgraph.
3 Marks
(b)
Define isomorphism. Determine whether the following pair of graphs are isomorphic.
4 Marks
(c)
Describe Königsberg Bridge Problem with respect to graph theory.
7 Marks
Gujarat Technological UniversityWinter 2025 Examination
GTU 3171611 Graph Theory and Combinatorics Winter 2025 Paper Solution & PDF
B.E. · IT Engineering · Semester 7 · Subject Code: 3171611
Total Marks70 MarksExternal theory exam
Passing Marks23 Marks33% minimum cutoff
Exam Duration2.5 Hours10:30 AM – 1:00 PM
Paper Structure5 QuestionsWith internal OR choices
Question 2
(a)
Define tree? List out the applications of tree?
3 Marks
(b)
What is graph coloring? Explain Greedy coloring.
4 Marks
(c)
Prove that the number of vertices of odd degree in a graph is always even. Also, take any graph and verify it.
7 Marks
OR OPTION
(c)
Prove that a simple graph with 𝑛 vertices and 𝑘 components can have most (𝑛−𝑘)(𝑛−𝑘+1) 2 edges.
7 Marks
Question 3
(a)
Differentiate Permutation & Combination with proper example.
3 Marks
(b)
In how many different ways can you arrange the letters of the word COMPUTER taking 4 at a time?
4 Marks
(c)
Explain the stable matching problem.
7 Marks
OR OPTION
(a)
Define edge vertex connectivity and edge connectivity. Give the relation between them.
3 Marks
(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?
4 Marks
(c)
Describe Hall’s marriage theorem.
7 Marks
Question 4
(a)
Explain Inclusion – Exclusion Principle.
3 Marks
(b)
What is Rook Polynomial? Explain expansion formula of it.
4 Marks
(c)
Find the length and shortest path between a and z in each of the weighted graphs Using Dijkstra’s algorithm.
7 Marks
OR OPTION
(a)
Write applications of Transport Network.
3 Marks
(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.
4 Marks
(c)
Explain Catalan numbers with suitable examples.
7 Marks
Question 5
(a)
Define de Bruijn graph.
3 Marks
(b)
What is recurrence relation? Explain different types of recurrence relation.
4 Marks
(c)
Solving Recurrence Relation an= 7an−1−10an−2 with a0=2 and a1=3.
7 Marks
OR OPTION
(a)
Define Derangements.
3 Marks
(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?
4 Marks
(c)
Solve the recurrence relation an=3an−1+2an=3an−1+2 subject to a0=1.
7 Marks
College Exam Groups
Studying for Graph Theory and Combinatorics?
Circulate this solved paper with KaTeX formulas and 1-click AI step solvers to your batchmates on WhatsApp or Telegram.
About this Examination Paper & Attribution
Official Gujarat Technological University (GTU) examination paper and step-by-step solutions 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.