Department of Mathematics
Module-4
Planar Graphs: Planar graphs, Kuratowski’s theorem (proof not required), Different
representations of planar graphs, Euler’s theorem, Geometric dual.
Graph Representations: Matrix representation of graphs-Adjacency matrix, Incidence Matrix,
Circuit Matrix, Path Matrix.
Q. No. Questions COs CL Marks
1 Define the following:
(i) Planar graph (ii) Embedding CO4 L2 8
(iii) Non-planar (iv) Kuratowski’s 2 graph
2 State Kuratowski’s theorem. Draw Kuratowski’s two graphs. CO4 L2 3
3 (i) Show that Petersen graph is non-planar.
(ii) Let 𝐺 be a planar graph. Then prove that it contains a vertex of CO4 L2 7
degree at most 5
4 State and prove Euler’s formula that gives the number of regions in CO4 L3 6
any planar graph.
5 Show that a connected planar graph with 𝑛 vertices and 𝑒 edges has CO4 L2 7
𝑒 − 𝑛 + 2 regions.
6 Describe the steps to find adjacency matrix and incidence matrix for CO4 L3 7
a directed graph with a simple example
7 If 𝐺 is a simple planar graph with at least three vertices, then show CO4 L2 7
that (i) 𝑒 ≤ 3𝑛 − 6 and (ii) 𝑒 ≤ 2𝑛 − 4; if 𝐺 is triangle free.
8 Explain the simple observation mode relationship between planar CO4 L3 8
graph and dual 𝐺 ∗
Draw the geometric dual of the given graph:
9 CO4 L2 6
10 Draw the geometric dual of the following graph.
CO4 L3 7
11 1. Draw the geometric dual of the graph G.
2. Write down the adjacency matrix for the graph G.
CO4 L2 7
12 i) Define geometric dual of a graph 𝐺.
ii) Draw the geometric dual of the graph 𝐺
CO4 L2 7
13 Write a note on path matrix. CO4 L2 4
Prove that two graphs 𝐺1 and 𝐺2 are isomorphic if and only if their
14 incidence matrices 𝐴(𝐺1 ) and 𝐴(𝐺2 ) differ only by permutations of CO4 L2 8
rows and columns.
15 Write the adjacency matrix and incidence matrix for the following
graph.
𝐴
CO4 L3 7
𝐸 𝐵
𝐷 𝐶
i) Define adjacency matrix.
ii) Find the adjacency matrix for the following graphs:
𝑣1 𝑣4
𝑣3
16 𝑣5 CO4 L2 7
𝑣2 𝑣3
𝑣4 𝑣5 𝑣1 𝑣2
Write down the Path matrix and Circuit matrix for the given graph
𝑣1 𝑣6
𝑣2
17 𝑣5 CO4 L2 7
𝑣3 𝑣4
i) Define path matrix and circuit matrix of a graph.
ii) Find the Path matrix from 𝑣3 to 𝑣5 for the following graph
𝑣3 𝑣6
18 𝑣4 CO4 L2 7
𝑣2
𝑣1 𝑣5
Describe the observations that can be made about circuit matrix
19 CO4 L2 7
𝐵(𝐺) 01 and graph 𝐺
Define adjacency matrix and incidence matrix. Write down the
adjacency matrix for the given graph 𝐺. 𝑣 3
𝑣2 𝑒4 𝑒8
20 𝑒3 𝑣4 CO4 L2 7
𝑒1 𝑒5
𝑣5 𝑒7
𝑒2
𝑣1 𝑣6
𝑒6
Module-5
Graph coloring: coloring- Chromatic number, Chromatic polynomial, Matchings, Coverings,
Four color problem and Five color problem. Greedy coloring algorithm.
Q. No. Questions COs CL Marks
Define Chromatic number. Prove that a graph with at least one
1 CO5 L3 6
edge is 2-chromatic if and only if it has no circuits of odd length.
2 Define chromatic polynomial and write the chromatic polynomial of CO5 L3 7
a graph with n vertices.
3 Prove that an 𝑛- vertex graph is a tree if and only if its chromatic CO5 L2 7
polynomial is 𝑃𝑛 (𝜆) = 𝜆(𝜆 − 1)𝑛−1
4 Prove that every tree with two or more vertices is 2-chromatic CO5 L2 6
Define chromatic number and chromatic polynomial of a graph. Find
the chromatic number and chromatic polynomial for following graph
𝑣1
5 CO5 L2 7
𝑣2
𝑣 𝑣3
⋮
𝑣𝑛
Explain the following for chromatic polynomial:
6 (i) Finding a maximal independent set CO5 L2 10
(ii) Finding all maximal independent set.
Define chromatic number of a graph. Find the chromatic polynomial
for the given graph.
7 CO5 L2 7
Define chromatic polynomial of a graph. Find the chromatic
polynomial of the graph.
𝑣1 𝑣2
8 CO5 L2 7
𝑣3 𝑣4
9 Define i) Complete Matching ii) Minimal Covering. Give one CO5 L2 6
example for each.
Define Matching and complete matching. Obtain two complete
matching from the given graph
d
a
10 b e CO5 L2 7
f
c
g
Define matching and complete matching. Find all the possible sets
of matching for the following graph. 𝑔1
𝑏1 𝑔2
11 CO5 L2 7
𝑏2 𝑔3
𝑏3 𝑔4
Define Covering and minimal covering of a graph.
Obtain two minimal coverings from the given graph.
𝑐 𝑑
12 CO5 L2 7
𝑎 𝑏
Define covering and minimal covering of a graph. Find the minimal
vertex covering and minimal edge covering of the following graph
𝑣2 𝑒2 𝑣3
𝑒1
13 𝑒7 𝑒3 CO5 L2 7
𝑣1 𝑒9 𝑣7 𝑒5 𝑣4
𝑒10 𝑒8 𝑒4
𝑣6 𝑒6 𝑣5
14 Prove that a covering of a graph is minimal if and only if 𝐺 contains CO5 L2 7
no paths of lengths three or more.
