BMS COLLEGE OF ENGINEERING, BANGALORE-19

DEPARTMENT OF MATHEMATICS
Course: STATISTICS AND DISCRETE MATHEMATICS Code: 22MA3BSSDM
UNIT-1: GRAPH THEORY
I. Fundamentals of graphs:

1. Define the following terms with an example for each

a) Graph, Order and Size of the graph
b) Finite graph, Infinite graph, Null graph, Trivial graph
c) Directed and Undirected graphs, Directed edge set
d) Labeled and Unlabeled graph
e) Directed Loop, Parallel directed edges/Multiple directed edges
f) Loop/Self Loop, Parallel/Multiple edges
g) Isolated vertex, Source and Sink
h) Adjacent vertices and adjacent edges
i) Incident of an edge
j) Simple Graph, free graph, Multi Graph and general graph
k) Complete graph (Or full graph), Kuratowski’s first graph
l) Bipartite graph
m) Complete Bipartite graph, Kuratowski’s second graph
n) Vertex degree, Degree sequence, Degree of the graph
o) In degree and Out degree
p) Isolated vertex, Pendent vertex
q) Regular graph (k-regular graph), Cubic graph, Peterson graph
r) K-dimensional hypercube,
2. Draw a diagram of the graph G(V,E) in each of the following cases:
1) V={A, B, C, D}, E={AB, AC, AD, CD}
2) V={v1, v2, v3, v4, v5}, E={v1v2, v1v3, v2v3, v4v5}
3) V={P, Q, R, S, T}, E={PQ, QR, QS}
4) V={A, B, C, D, E, F}, E={AD, AF, DF, CB, CE, BE}
3. Which of the following are complete graphs?

4. Which of the following are Bipartite graphs?

 5. Which of the following are Complete Bipartite Graphs?

6. Prove that a complete graph with n vertices, namely Kn, has n(n-1)/2 edges.
7. Verify whether simple graph of order 4 and size 7 and a complete graph of order 4
and size 5 do exist?
8. How many vertices and how many edges are there in the complete bipartite graphs
K4,7 and K7,11 ?
9. If the graph Kr,12 has 72 edges, what is r?
10. Prove that a simple graph of order 4 and size 5 cannot be a bipartite graph.

Property: Let G=(V,E) be a simple graph of order |V|=n and size |E|=m. If G is a bipartite
graph then 4m≤n2.

First theorem of graph theory: In every digraph D, the sum of the out-degrees of all vertices
is equal to the sum of the in-degrees of all vertices, each sum being equal to the number of
edges in D.

Handshaking property: The sum of the degrees of all the vertices in a graph is an even
number: and this number is equal to twice the number of edges in the graph.

Property: In every graph, the number of vertices of odd degrees is even.

11. Verify the First theorem of Digraph for the following graphs

12. Verify the Handshaking property to the following graphs

 13. Are the following graphs regular?

14. Can there be a graph consisting of the vertices A, B, C, D with deg(A)=2, deg(B)=3,
deg(C)=2 and deg(D)=2?
15. Can there be a graph with 12 vertices such that two of the vertices have degree 3
each and the remaining 10 vertices have degree 4 each?
16. For a graph G=(V,E), what is the largest possible value for |V|, if |E|=19 and deg(v)
≥4 for all v in V?
17. Prove that the hypercube Q3 is a bipartite graph which is not a complete bipartite
graph.
18. Prove that k-dimensional hypercube Qk has k2k-1 edges. Determine the number of
edges in Q8.
19. What is the dimension of the hypercube with 524288 edges?
20. How many vertices are there in a hypercube with 4980736 edges?
21. Determine the order |V| of the graph in the following cases
i. G is a cubic graph with 9 edges.
ii. G is regular with 15 edges.
iii. G has 10 edges with 2 vertices of degree 4 and all other vertices of degree 3.
22. Let G be a graph of order 9 such that each vertex has degree 5 or 6. Prove that at
least 5 vertices have degree 6 or atleast 6 vertices have degree 5.
23. Prove that there is no graph with 28 edges and 12 vertices in the following cases
a) The degree of a vertex is either 3 or 4.
b) The degree of a vertex is either 3 or 6.
24. For a graph with n vertices and m edges, if δ is the minimum and ∆ is the maximum
2𝑚
of the degrees of vertices, Prove that δ ≤ ≤∆
𝑛
II. Subgraphs
1. Define subgraph with an example
2. Define Spanning subgraph with an example
3. Induced subgraph with an example
4. Edge disjoint subgraphs with an example
5. Vertex disjoint subgraphs with an example
 6. Given a graph G1, can there exist a graph G2 such that G1 is a subgraph of G2 but
not a spanning subgraph of G2 and yet G1 and G2 have the same size?
7. Consider the graph G shown in figure
i. Verify that the graph G1 is an induced subgraph of G. Is this a spanning
subgraph of G?
ii. Draw the subgraph G2 of G induced by the set V2={v3, v4, v6, v8,v9}.

8. Consider the graph G shown in figure. Verify that the graphs G1, G2 and G3 are
induced subgraphs of G.

9. For the given graph, find two edge-disjoint subgraphs and two vertex-disjoint
subgraphs.

III. Isomorphism
1. Define isomorphism with an example
2. Verify the following graphs are isomorphic or not

a)

b)
 c)

d)

e)
3. Define the following terms with an example for each
a) Walk, Length of the walk, Open walk, closed walk
b) Trail and Circuit, Path and Cycle
c) Open
4. For the graph shown in figure, indicate the nature of the following walks.
(i) v1e1v2e2v3e2v2 (ii) v4e7v1e1v2e2v3e3v4e4v5
(iii) v1e1v2e2v3e3v3e7v1
(iv) v1e1v2e2v3e3v4e4v5 (v) v6e5v5e4v4e3v3e2v2e1v1e7v4e6v6

5. From the graph find all paths from vertex A to vertex R. Also indicate their lengths?
 6. Determine the number of different paths of length 2 in the graph shown below?

7. Find all the cycles present in the graph

8. If G is a simple graph in which every vertex has degree at least k, prove that G
contains a path of length at least k.
9. Prove the following:
i. A path with n vertices is of length n-1
ii. If a cycle has n vertices it has n edges
iii. The degree of every vertex in a cycle is two.
IV. Connected Graphs
1. Define connected and disconnected graphs with an example
2. Define the component of the graph
3. Distance of the path
4. Find the distance between the vertex v1 and the vertices v3, v5, v6 and v11 in the
following graph.

5. Prove that if a graph has exactly two vertices of odd degree, then there must be a
path connecting these vertices.
6. Prove that a simple graph with n vertices and k components can have at most
1
( n − k )( n − k − 1) number of edges.
2
1
7. Prove that if m  ( n − 1)( n − 2 ) then a simple graph with n vertices and m edges is
2
connected.
8. Prove that A connected graph with n vertices has at least n-1 edges.
9. Prove that A graph G is disconnected if and only if its vertex set V can be partitioned
into two non-empty disjoint subsets V1 and V2 such that there exists no edge in G
whose one end vertex is in V1 and the other is in V2
10. Define Euler circuit and Euler Trail
11. Define Euler/Eulerian graph and Semi-Eulerian graph
12. Find the following graphs are Euler or Semi-Euler graphs

a)

b)

c)

d)
13. Prove that a connected graph G has a Euler circuit if an only if all vertices of G are
of even degree.
14. Prove that A connected graph G has a Euler circuit if and only if G can be
decomposed into edge-disjoint cycles.
15. Prove that a connected graph G remains connected after removing an edge e from G
if and only if e is a part of some cycle in G.
16. Let G be a disconnected graph of even order n with two components each of which
is complete. Prove that G has a minimum of n(n-2)/4 edges.
17. Prove that the complete graph Kn is not a tree when n > 2. And also Prove that the
complete bipartite graph Kr,s is not a tree when r≥2.
18. Prove that a graph with n vertices, n-1 edges and no cycles is connected.
19. Define Hamilton Cycles and Hamilton Paths
20. Define Hamilton or Hamiltonian graphs
21. Verify the following are Hamiltonian graphs or Hamiltonian paths

a)
 b)

c)

d)
22. Prove that the following graphs are Hamiltonian but not Eulerian

23. Which of the following graphs are Hamiltonian or Eulerian?

24. Exhibit the following:

 i. A graph which has both a Euler circuit and a Hamilton cycle.
ii. A graph which has a Euler circuit but no Hamilton cycle
iii. A graph which has a Hamilton cycle but no Euler circuit.
iv. A graph which has neither a Hamilton cycle nor a Euler circuit.
V. TREES
1. Define tree, leaf, forest
2. Define spanning tree (Skeleton or Scaffolding)
3. Find all the spanning trees of the following graphs
4. Define weighted graph and weight of the tree
5. Define minimal spanning tree
6. Let F be a forest with k components (trees). If n is the number of vertices and m is
the number of edges in F, prove that n=m+k.
7. Let T1 = (V1, E1) and T2 = (V2, E2) be two trees. If |E1| = 19 and |V2|=3|V1|,
determine |V1|, |V2| and |E2|.
8. If a tree has 2020 vertices, find the sum of the degrees of the vertices.
9. Suppose that a tree T has two vertices of degree 2, four vertices of degree 3 and
three vertices of degree 4. Find the number of pendant vertices in T.
10. Suppose that a tree T has N1 vertices of degree 1, N2 vertices of degree 2, N3 vertices
of degree 3,… Nk vertices of degree k. Prove that N1=2+N3+2N4+3N5+…….(k-2)Nk
11. If a tree T has four vertices of degree 2, one vertex of degree 3, two vertices of
degree 4 and one vertex of degree 5, find the number of leaves in T
12.
13. Write all possible spanning trees of the following graphs

a.

b.

c.
14. Using Kruskal’s algorithm find the minimal spanning tree of the following graphs
 i.

ii.

iii.

iv.
v. Eight cities A, B, C, D, E, F, G, H are required to be connected by a new railway
network. The possible tracks and the cost of involved to lay them (in crores of
rupees) are summarized in the following table. Determine a railway network of
minimal cost that connects all these cities.
TRACK AB AD AG BC CD CE DF EF FG FH GH

COST 155 145 120 145 150 95 100 150 140 150 160

15. Using Dijkstra’s algorithm find shortest path and its weight
i. Find shortest part from vertex O to all remaining
ii. Find shortest part from vertex S to all remaining

iii. Find shortest part from vertex A to all remaining

iv. Find shortest part from vertex O to all remaining

v. Find shortest part from vertex 3 to all remaining

vi. Find shortest part from vertex a to all remaining

VI. MATRICES OF THE GRAPHS
1. Define Incidence matrix with observations
2. Define Adjacency matrix with observations
3. Write the incidence matrix of the given graph

4. Draw the graph G whose incidence matrix is given by

i.

ii.
iii.
5. Does there exist a graph G corresponding to this incidence matrix A(G) is
given by

6. Obtain the incidence matrix for the graph whose adjacency matrix is given
below.
a b c d e
a 0 1 0 1 0
b 1 0 1 0 1
 
X (G ) = c  0 1 0 0 1
 
d 1 0 0 0 1
e  0 1 1 1 0 
7. For the given adjacency matrix A(G) , construct incidence matrix and also
write any three observations on incidence matrix
0 0 1 0 1 
0 0 0 0 1 
 
A(G ) =  1 1 0 1 0 
 
0 0 1 0 0 
 1 1 0 0 0 