23MAT116-Discrete Mathematics
Tutorial-5
1) Can a graph exist with 5 vertices of degrees 1, 2, 3, 4 and 5? Justify.
2) How many vertices does a regular graph of degree four with 10 edges have?
3) A simple graph G has 24 edges and the degree of each vertex is 4. Find the number of vertices.
4) A simple graph contains 35 edges, four vertices of degree 5, five vertices of degree 4 and four
vertices of degree 3. Find the number of vertices with degree 2.
5) Prove that the following graphs G and H are isomorphic:
i.
(b)
6) Draw the following graphs and determine how many edges each has.
i. K4
ii. K3,2
iii. K1,5
7) For some positive integers m, n, how many edges are in
i. Kn ?
ii. Km,n?
8) If a graph has five vertices of degree 4 and four vertices of degree 3, how many
edges does it have?
9) A graph has 26 vertices and 58 edges. There are five vertices of degree 4, six vertices of
degree 5, and seven vertices of degree 6. If the remaining vertices all have the same degree,
what is this degree?
10) A graph has 24 vertices and 30 edges. It has five vertices of degree 4, seven pendant vertices,
and seven vertices of degree 2. All other vertices have degree 3 or 4. How many vertices of
degree 4 are there?
11) Use graph theory to explain why at any party an even number of people speak to an odd
number of people.
12) Can there exist a graph on 13 vertices and 31 edges, with three vertices of de- gree 1, and
seven vertices of degree 4? Explain.
13) If a graph G has 15 edges and all vertices of the same degree d, what are the
possible values of d? Describe briefly each graph.
14) Given the following degree sequences either construct a graph with such a degree
sequence, or explain why this would be impossible.
i. 1, 1, 1, 1, 1, 1
ii. 5, 4, 3, 2, 1
iii. 6, 6, 4, 2, 2, 2, 2, 1
15) How many (simple) graphs are there with exactly n vertices?
16) What is the maximum number of vertices on a graph that has 35 edges and every
vertex has degree ≥ 3?
17) Suppose all vertices in a graph, G, have odd degree, k. Prove k divides |E(G)|.
18) Using graph theory, explain whether or not it is possible for each person, in a group of 15
individuals, to have exactly three friends. (Assume that friendship is a symmetric relation, i.e.
friendship goes both ways.)
19) Using Dijkstra’s Algorithm find the shortest path and the length of the shortest path from the
vertex a to the vertex z of the following weighted graph.
20) Using Dijkstra’s Algorithm find the shortest path and the length of the shortest
path from the vertex a to the vertex z of the following weighted graph.
21) Which of the following graphs are Hamiltonian? If they are Hamiltonian identify a
Hamiltonian cycle. If they are not, explain briefly why.
(a)
(b)
(c)
(d)
22) Does there exist a graph that is both Eulerian and Hamiltonian? If so, find one. If
not, explain why this is impossible.
