COMPUTER SCIENCE AND ENGINEERING

CODE COURSE NAME CATEGORY L T P CREDIT

MAT 206 GRAPH THEORY BSC 3 1 0 4

Preamble: This course introduces fundamental concepts in Graph Theory, including

properties and characterisation of graph/trees and graph theoretic algorithms, which are
widely used in Mathematical modelling and has got applications across Computer Science
and other branches in Engineering.

Prerequisite: The topics covered under the course Discrete Mathematical Structures (MAT
203 )

Course Outcomes: After the completion of the course the student will be able to

Explain vertices and their properties, types of paths, classification of graphs and
CO 1
trees & their properties. (Cognitive Knowledge Level: Understand)
Demonstrate the fundamental theorems on Eulerian and Hamiltonian graphs.
CO 2
(Cognitive Knowledge Level: Understand)

Illustrate the working of Prim’s and Kruskal’s algorithms for finding minimum cost
CO 3 spanning tree and Dijkstra’s and Floyd-Warshall algorithms for finding shortest
paths. (Cognitive Knowledge Level: Apply)
Explain planar graphs, their properties and an application for planar graphs.
CO 4
(Cognitive Knowledge Level: Apply)

Illustrate how one can represent a graph in a computer. (Cognitive Knowledge

CO 5
Level: Apply)

Explain the Vertex Color problem in graphs and illustrate an example application
CO 6
for vertex coloring. (Cognitive Knowledge Level: Apply)
 COMPUTER SCIENCE AND ENGINEERING
Mapping of course outcomes with program outcomes

PO PO PO PO PO
PO 2 PO 3 PO 4 PO 7 PO 10 PO 11 PO 12
1 5 6 8 9

CO 1 √ √ √ √ √

CO 2 √ √ √ √ √ √

CO 3 √ √ √ √ √ √

CO 4 √ √ √ √ √ √

CO 5 √ √ √ √ √

CO 6 √ √ √ √ √ √

Abstract POs defined by National Board of Accreditation

PO# Broad PO PO# Broad PO

PO1 Engineering Knowledge PO7 Environment and Sustainability

PO2 Problem Analysis PO8 Ethics

PO3 Design/Development of solutions PO9 Individual and team work

Conduct investigations of complex
PO4 PO10 Communication
problems
PO5 Modern tool usage PO11 Project Management and Finance
PO6 The Engineer and Society PO12 Life long learning

Assessment Pattern

Continuous Assessment Tests (%) End Semester

Bloom’s Category
Examination (%)
1 2
Remember 30 30 30

Understand 30 30 30
Apply 40 40 40

Analyse
Evaluate

Create
 COMPUTER SCIENCE AND ENGINEERING

Mark Distribution

Total Marks CIE Marks ESE Marks ESE Duration

150 50 100 3 hours

Continuous Internal Evaluation Pattern:

Attendance : 10 marks

Continuous Assessment Tests : 25 marks

Continuous Assessment Assignment : 15 marks

Internal Examination Pattern:

Each of the two internal examinations has to be conducted out of 50 marks

First Internal Examination shall be preferably conducted after completing the first half of the
syllabus and the Second Internal Examination shall be preferably conducted after completing
remaining part of the syllabus.

There will be two parts: Part A and Part B. Part A contains 5 questions (preferably, 2
questions each from the completed modules and 1 question from the partly covered module),
having 3 marks for each question adding up to 15 marks for part A. Students should answer
all questions from Part A. Part B contains 7 questions (preferably, 3 questions each from the
completed modules and 1 question from the partly covered module), each with 7 marks. Out
of the 7 questions in Part B, a student should answer any 5.

End Semester Examination Pattern: There will be two parts; Part A and Part B. Part A
contain 10 questions with 2 questions from each module, having 3 marks for each question.
Students should answer all questions. Part B contains 2 questions from each module of which
student should answer anyone. Each question can have maximum 2 sub-divisions and carries
14 marks.
 COMPUTER SCIENCE AND ENGINEERING

Syllabus

Module 1

Introduction to Graphs : Introduction- Basic definition – Application of graphs – finite,

infinite and bipartite graphs – Incidence and Degree – Isolated vertex, pendant
vertex and Null graph. Paths and circuits – Isomorphism, sub graphs, walks, paths
and circuits, connected graphs, disconnected graphs and components.

Module 2

Eulerian and Hamiltonian graphs : Euler graphs, Operations on graphs, Hamiltonian paths
and circuits, Travelling salesman problem. Directed graphs – types of digraphs, Digraphs and
binary relation, Directed paths, Fleury’s algorithm.

Module 3

Trees and Graph Algorithms : Trees – properties, pendant vertex, Distance and centres in a
tree - Rooted and binary trees, counting trees, spanning trees, Prim’s algorithm and Kruskal’s
algorithm, Dijkstra’s shortest path algorithm, Floyd-Warshall shortest path algorithm.

Module 4

Connectivity and Planar Graphs : Vertex Connectivity, Edge Connectivity, Cut set and Cut
Vertices, Fundamental circuits, Planar graphs, Kuratowski’s theorem (proof not required),
Different representations of planar graphs, Euler's theorem, Geometric dual.

Module 5

Graph Representations and Vertex Colouring : Matrix representation of graphs-

Adjacency matrix, Incidence Matrix, Circuit Matrix, Path Matrix. Coloring- Chromatic
number, Chromatic polynomial, Matchings, Coverings, Four color problem and Five color
problem. Greedy colouring algorithm.

Text book:

1. Narsingh Deo, Graph theory, PHI,1979

Reference Books:

1. R. Diestel, Graph Theory, free online edition, 2016: diestel-graph-theory.com/

basic.html.
2. Douglas B. West, Introduction to Graph Theory, Prentice Hall India Ltd.,2001
3. Robin J. Wilson, Introduction to Graph Theory, Longman Group Ltd.,2010
4. J.A. Bondy and U.S.R. Murty. Graph theory with Applications
 COMPUTER SCIENCE AND ENGINEERING

Sample Course Level Assessment Questions.

Course Outcome 1 (CO1):

1. Differentiate a walk, path and circuit in a graph.

2. Is it possible to construct a graph with 12 vertices such that two of the vertices have
degree 3 and the remaining vertices have degree 4? Justify

3. Prove that a simple graph with n vertices must be connected, if it has more than
(n − 1)(n − 2)
edges.
2
4. Prove the statement: If a graph (connected or disconnected) has exactly two odd degree,
then there must be a path joining these two vertices.

Course Outcome 2 (CO2):

1. Define Hamiltonian circuit and Euler graph. Give one example for each.

2. Define directed graphs. Differentiate between symmetric digraphs and asymmetric

digraphs.

3. Prove that a connected graph G is an Euler graph if all vertices of G are of even degree.

4. Prove that a graph G of n vertices always has a Hamiltonian path if the sum of the degrees
of every pair of vertices Vi, Vj in G satisfies the condition d(Vi) + d(Vj) =n−1
Course Outcome 3 (CO3):

1. Discuss the centre of a tree with suitable example.

(n + 1)
2. Define binary tree. Then prove that number of pendant vertices in a binary tree is
2
3. Prove that a tree with n vertices has n − 1 edges.

4. Explain Floyd Warshall algorithm.

5. Run Dijkstra’s algorithm on the following directed graph, starting at vertex S.

 COMPUTER SCIENCE AND ENGINEERING

Course Outcome 4 (CO4):

1. Define edge connectivity, vertex connectivity and separable graphs. Give an example for
each.

2. Prove that a connected graph with n vertices and e edges has e − n + 2 edges.

3. Prove the statement: Every cut set in a connected graph G must also contain at least one
branch of every spanning tree of G.

4. Draw the geometrical dual (G*) of the graph given below, also check whether G and G*
are self-duals or not, substantiate your answer clearly.

Course Outcome 5 (CO5):

1. Show that if A(G) is an incidence matrix of a connected graph G with n vertices, then
rank of A(G) is n−1.

2. Show that if B is a cycle matrix of a connected graph G with n vertices and m edges, then
rank B = m−n+1.

3. Derive the relations between the reduced incidence matrix, the fundamental cycle matrix,
and the fundamental cut-set matrix of a graph G.

4. Characterize simple, self-dual graphs in terms of their cycle and cut-set matrices.

Course Outcome 6 (CO6):

1. Show that an n vertex graph is a tree iff its chromatic polynomial is P n(λ) = λ(λ − 1)n−1

2. Prove the statement: “A covering g of a graph is minimal if g contains no path of length

three or more.”

3. Find the chromatic polynomial of the graph

 COMPUTER SCIENCE AND ENGINEERING
Model Question paper

QP
Code : Total Pages: 4

Reg No.:_______________ Name:__________________________

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY

IV SEMESTER B.TECH DEGREE EXAMINATION, MONTH and YEAR
Course Code: MAT 206
Course Name: GRAPH THEORY
Max. Marks: 100 Duration: 3 Hours
PART A
Answer all questions, each carries3 marks. Mark
s

1 Construct a simple graph of 12 vertices with two of them having degree 1, (3)
three having degree 3 and the remaining seven having degree 10.
2 What is the largest number of vertices in a graph with 35 edges, if all (3)
vertices are of degree at least 3 ?
3 Define a Euler graph. Give an example of Eulerian graph which is not (3)
Hamiltonian
4 Give an example of a strongly connected simple digraph without a directed (3)
Hamiltonian path.
5 What is the sum of the degrees of any tree of n vertices? (3)
6 How many spanning trees are there for the following graph (3)
 COMPUTER SCIENCE AND ENGINEERING
7 Show that in a simple connected planar graph G having V-vertices, E-edges, (3)
and no triangles E <= 3V - 6.
8 Let G be the following disconnected planar graph. Draw its dual G*, and the (3)
dual of the dual (G*)*.

9 Consider the circuit matrix B and incidence matrix A of a simple connected (3)
graph whose columns are arranged using the same order of edges. Prove that
every row of B is orthogonal to every row of A?
10 A graph is critical if the removal of any one of its vertices (and the edges (3)
adjacent to that vertex) results in a graph with a lower chromatic number.
Show that Kn is critical for all n > 1.
PART B
Answer any one Question from each module. Each question carries 14 Marks
11 a) Prove that for any simple graph with at least two vertices has two vertices of (6)
the same degree.
b) Prove that in a complete graph with n vertices there are (n-1)/2 edge disjoint (8)
Hamiltonian circuits and n >= 3
OR
 OR
COMPUTER SCIENCE AND ENGINEERING
​ etermine whether the following graphs ​G​1​ = (V​1​, E​1​)​ and ​G​2​ = (V​2​, E​2​) ​are isomorphic
12. a) D
12 a) Determine whether the following graphs G1 = (V1, E1) and G2 = (V2, E2) are (6)
or not. Give justification. (6)
isomorphic or not. Give justification.

b) P b) that
​ rove Prove that a graph
a simple simplewith ​n​ vertices
graph with nand ​k ​ components
vertices and k components
can have atcan have
most at (n-(8)
​(n-k)
k+1)/2​ edges.
most (n-k) (n-k+1)/2 edges (8)
13Leta)​S ​bLet
13. a) e a Ssetbeofa 5set
elements. Construct
of 5 elements. Construct ​whose
a grapha​Ggraph G vertices are subsets
whose vertices of ​S ​of size
are subsets (8)
2 and twoofsuch
S ofsubsets are two
size 2 and adjacent
such in ​G​ if they
subsets are disjoint.
are adjacent in G if they are disjoint. (8)
i. Drawi.theDraw ​G​.graph G.
graphthe
ii. How ii.
many edges
How manymust musttobe​G​ added
be added
edges ​ to order
in ordertoforG​Gin have afor
Hamiltonian
G to havecycle?
a
b) Let ​G​ be a graph with exactly
Hamiltonian two connected components, both being Eulerian. What is
cycle?
theb)
minimum
Let G number of edges
be a graph withthat need totwo
exactly be added to ​G​ to
connected obtain an Eulerian
components, graph? (6)
both being
Eulerian. What is the minimum number of edges that need to be added to G ​(6)
to obtain an Eulerian graph?
OR
14. a) Show that a ​k​-connected graph with no hamiltonian
OR cycle has an independent set of size
14k +a)1​. Show that a k-connected graph with no hamiltonian cycle has an (8)
(8)
b) independent set of size k + 1. (6)
i.b) Let ​Gi.​beLet
a graph
G bethat has exactly
a graph twoexactly
that has connected
two components, both being both
connected components,
Hamiltonian
beinggraphs. Find thegraphs.
Hamiltonian minimumFindnumber of edgesnumber
the minimum that oneofneeds to that
edges add to
G​ to obtain
oneaneeds
Hamiltonian
to add tograph.
G to obtain a Hamiltonian graph. (6)
ii. For which
ii. Forvalues
which ​n ​the graph
of values ​n ​(hyper-cube
of n ​Qthe on ​n ​vertices)onis nEulerian.
graph Qn (hyper-cube vertices) is
Eulerian.
15 a) A tree T has at least one vertex v of degree 4, and at least one vertex w of (5)
degree 3. Prove that T has at least 5 leaves.
 COMPUTER SCIENCE AND ENGINEERING
b) Write Dijkstra’s shortest path algorithm. (9)
Consider the following weighted directed graph G.

Find the shortest path between a and every other vertices in G using
Dijkstra’s shortest path algorithm.
OR
16 a) Define pendent vertices in a binary tree? Prove that the number of pendent (5)
vertices in a binary tree with n vertices is (n+1)/2.
b) (9)
Write Prim’s algorithm for finding minimum spanning tree.
Find a minimum spanning tree in the following weighted graph, using
Prim's algorithm.

Determine the number of minimum spanning trees for the given graph.
 COMPUTER SCIENCE AND ENGINEERING
17 a) i. State and prove Euler's Theorem relating the number of faces, edges and (9)
vertices for a planar graph.
ii. If G is a 5-regular simple graph and |V| = 10, prove that G is non-planar.
b) Let G be a connected graph and e an edge of G. Show that e is a cut-edge if (5)
and only if e belongs to every spanning tree.
OR OR
18 a) 18. a) State
State Kuratowski's
Kuratowski's theorem,
theorem, andituse
and use it to show
to show thatgraph
that the the graph G below
G below is notis not
(9)planar.
Draw
planar. G on
Draw the the
G on plane without
plane edges
without crossing.
edges YourYour
crossing. drawing should
drawing use the labelling of
should
thelabelling
use the vertices of
given.
the vertices given. (9)

b) Let G
b) be
Leta​Gconnected graph graph
​ be a connected and e and
an edge of G.ofShow
​e​ an edge that that
​G​. Show e belongs to ato a(5)
​e​ belongs loop if and
loop if only
and only if e belongs
if ​e​ belongs to notospanning
no spanning
tree.tree. (5)
19 a) 19.
Define the circuit
a) Define matrix
the circuit B(G)​Bof
matrix a ​ connected
(G) graphgraph
of a connected G with n vertices
​G​ with and and
​n​ vertices e (7)
​e​ edges with
edgesanwith an example.
example. Prove Prove that
that the theofrank
rank of​ is
​B(G) B(G) is ​.e-n+1
​e-n+1
b) Give
(7) the definition of the chromatic polynomial PG(k). Directly from the (7)
definition, prove
b) Give the that theofchromatic
definition polynomials
the chromatic of ​P
polynomial ​
and
W​Gn(k) Cn satisfy
​. Directly fromthe
the definition,
identity PWnthat
prove (k) =the
k Pchromatic polynomials of ​W​n​ and ​C​n​ satisfy the identity ​P​Wn​(k) = k P​Cn-1
Cn-1 (k – 1).

(k – 1).​ (7)
OR
OR
20 a) Define the incidence matrix of a graph G with an example. Prove that the (4)
20. a) of
rank Define the incidence
an incidence matrixmatrix
of a connected ​G ​with
of a graphgraph an nexample.
with Prove
vertices is n-1. that the rank of an
incidence matrix of a connected graph with ​n​ vertices is ​n-1. ​ (4)
b) (10)
i. A graph ​G has chromatic polynomial ​P​G​(k) = k​4​-4k​3​+5k​2​-2k​. How many vertices
and edges does ​G​ have? Is ​G​ bipartite? Justify your answers.
 COMPUTER SCIENCE AND ENGINEERING
b) i. A graph G has chromatic polynomial PG(k) = k4-4k3+5k2-2k. How
many vertices and edges does G have? Is G bipartite? Justify your
answers.
ii. Find a maximum matching in the graph below and use Hall's theorem
to show that it is indeed maximum.

(10)

****

Assignments

Assignment must include applications of the above theory in Computer Science.

 COMPUTER SCIENCE AND ENGINEERING
Teaching Plan

No. of
No Topic
Lectures

1 Module-I (Introduction to Graphs) (8)

1. Introduction- Basic definition – Application of graphs – finite and 1

infinite graphs, bipartite graphs,

2. Incidence and Degree – Isolated vertex, pendent vertex and Null graph 1

3. Paths and circuits 1

4. Isomorphism 1

5. Sub graphs, walks 1

6. Paths and circuits 1

7. Connected graphs. 1

8. Disconnected graphs and components 1

2 Module-II (Eulerian and Hamiltonian graphs) (8)

1. Euler graphs 1

2. Operations on graphs 1

3. Hamiltonian paths and circuits 1

4. Hamiltonian paths circuits 1

5. Travelling salesman problem 1

6. Directed graphs – types of digraphs, 1

7. Digraphs and binary relation, Directed paths 1

8. Fleury’s algorithm 1

3 Module-III (Trees and Graph Algorithms) (11)

1. Trees – properties 1

2. Trees – properties 1

3. Trees – properties, pendent vertex 1

4. Distance and centres in a tree 1

 COMPUTER SCIENCE AND ENGINEERING
5. Rooted and binary tree 1

6. Counting trees 1

7. Spanning trees, Fundamental circuits 1

8. Prim’s algorithm 1

9. Kruskal’s algorithm 1

10. Dijkstra’s shortest path algorithm 1

11. Floyd-Warshall shortest path algorithm 1

4 Module-IV (Connectivity and Planar Graphs) (9)

1. Vertex Connectivity, Edge Connectivity 1

2. Cut set and Cut Vertices 1

3. Fundamental circuits 1

4. Fundamental circuits 1

5. Planar graphs 1

6. Kuratowski’s theorem 1

7. Different representations of planar graphs 1

8. Euler's theorem 1

9. Geometric dual 1

5 Module-V (Graph Representations and Vertex Colouring) (9)

1. Matrix representation of graphs- Adjacency matrix, Incidence Matrix 1

2. Circuit Matrix, Path Matrix 1

3. Colouring- chromatic number, 1

4. Chromatic polynomial 1

5. Matching 1

6. Covering 1

7. Four colour problem and five colour problem 1

 COMPUTER SCIENCE AND ENGINEERING
8. Four colour problem and five colour problem 1

9. Greedy colouring algorithm. 1