Module 4

Part A
SL Question Marks
No.
1 How many edges does a graph have if its degree sequence is 4, 3, 3, 2, 2? Draw such a graph. 2

2 What is the degree sequence of 𝐾𝑛 , where n is a positive integer? Explain your answer. 2

3 What is the degree sequence of the bipartite graph 𝐾𝑚,𝑛 , where m and n are positive integers? 2
Explain your answer.

4 What is the chromatic number of 𝐾𝑛 ? 2

5 Define Euler Circuit with an example. 2

6 Define Hamiltonian Circuit with an example. 2

7 How many vertices does a regular graph of degree four with 10 edges have? 2

8 What does it mean for two simple graphs to be isomorphic? Explain with an example 2

9 State Hall’s marriage theorem. 2

10 Explain planar graph with an example. Write down one application of planar graphs in real 2
life.

11 What is the chromatic number a complete graph with 15 vertices? 2

12 Is the following polynomial a chromatic polynomial? 2

𝑥 2 2 + 2𝑥 − 3
Justify your answer.
13 Define maximal matching and maximum matching with an example. 2
14 Define a perfect matching. Is every maximal matching perfect matching? explain with an 2
example.

15 Define binary tree with an example. 2

16 What will be the chromatic number star graph 𝑆𝑛 and a cyclic graph 𝐶2𝑛 ? 2

17 Which of the graphs 𝐾𝑛 , 𝐶𝑛 , and 𝑊𝑛 are bipartite? Answer with explanation 2

18 Use an adjacency matrix to represent the graph 2

19 Use an incidence matrix to represent the graph 2

20 Check whether the following two graphs are isomorphic or not. 2

 Part B

SL Question Marks
1 Does the graph given below have a Hamilton path? If so, find such a path. If it does 5
not, give an argument to show why no such path exists.

2 With the help of at least two different examples, explain how graph colouring can be 5
used in modelling.

3 Check if the graph given below has a Hamilton path? If so, find such a path. If it does 5
not, give an argument to show why no such path exists.

4 Check if the graph given below has a Hamilton path? If so, find such a path. If it does 5
not, give an argument to show why no such path exists.

5 Find Chromatic Polynomial of the following graph and hence find its chromatic 5
number:
6 Find chromatic polynomial of a connected graph on three vertices. 5

7 Draw the graph whose incidence matrix is 5

0 0 1 −1 1
−1 1 0 0 0
0 0 0 0 0
1 0 0 0 −1
0 1 0 0 0
[0 0 −1 1 0]

8 Draw the graph represented by the given adjacency matrix:

0 0 0 0 1
0 0 1 0 0
1 0 0 0 0
0 0 1 0 0
[0 1 0 0 0]

9 Show that 𝐾3,3 is not planar. 5

10 Write down the Euler’s Formula for planar graphs and verify the result for the 5
following graph

11 Show that if 𝜒(𝐺) = 2, then G is bipartite. 5

12 How many vertices and how many edges do these graphs 5
have?
a) 𝐾𝑛
b) 𝐶𝑛
c) 𝑊𝑛
d) 𝐾𝑚,𝑛
e) 𝑄𝑛

13 Prove that the cyclic graph 𝐶2𝑛+1 is not Bipartite. 5

14 Determine whether two given graphs are isomorphic. 5

15 Show that a connected graph is an Euler graph if and only if every vertex of the
graph has an even degree.
 Part C

SL Question Marks

1 In the graph given below, find the length of a shortest path between a and z in the given 10
weighted graph.

2 Find the chromatic number of the given graph: 10

3 In the graph given below, find the length of a shortest path between a and z in the given 10
weighted graph.
4 Find the chromatic number of the given graph: 10

5 Answer the following about the rooted tree illustrated. 10

a) Which vertex is the root?

b) Which vertices are internal?
c) Which vertices are leaves?
d) Which vertices are children of j?
e) Which vertex is the parent of h?
f) Which vertices are siblings of o?
g) Which vertices are ancestors of m?
h) Which vertices are descendants of b?

6 Find a spanning tree for the graph shown by removing edges in simple circuits 10
7 Find a spanning tree for the graph shown by removing edges in simple circuits 10

8 Use Prim’s algorithm to find a minimum spanning tree for the given weighted graph: 10

9 Draw the graph whose incidence matrix is 10

0 0 1 −1 1
−1 1 0 0 0
0 0 0 0 0
1 0 0 0 −1
0 1 0 0 0
[0 0 −1 1 0]

10 Find the minimal spanning tree (MST) using Kruskal’s algorithm for the following graph 10
11 Find the minimal spanning tree (MST) using Kruskal’s algorithm for the following graph 10

12 Find the minimal spanning tree (MST) using Kruskal’s algorithm for the following graph 10

13 Find the minimal spanning tree (MST) using Prim’s algorithm for the following graph 10
14 Find the shortest path from A vertex to T vertex using Dijkstra’s algorithm 10

15 Find the chromatic number of the given graph: 10

16 Solve the traveling salesperson problem for this graph by finding the total weight of all 10
Hamilton circuits and determining a circuit with minimum total weight.

17 Solve the traveling salesperson problem for this graph by finding the total weight of all 10
Hamilton circuits and determining a circuit with minimum total weight.

18 Find a route with the least total airfare that visits each of the cities in this graph, where the 10
weight on an edge is the least price available for a flight between the two cities.
19 Determine whether the following graph G is planar or not. 10

20 Suppose that a connected planar simple graph with 𝑒 edges and 𝑣 vertices contains no 10
5𝑣 10
simple circuits of length 4 or less. Show that 𝑒 ≤ 3 − 3 , 𝑣 ≥ 4 if.