Government Engineering College, Kaimur

Department of Applied Science & Humanities (Mathematics)

Name of Faculty: Dr. Rajnesh Kumar

Note: Following are the problems which are required to be done by the students for an overall
understanding of the topics.

1. Prove that in a non-directed graph, the total number of odd degree vertices is even.
2. Show that the maximum number of edges in a simple graph with 𝑛 vertices is n(n-1)/2.
3. Find the number of spanning subgraphs in 𝐾6 and draw all possible subgraphs of 𝐾3 .
4. Prove that a simple graph with 𝑛 vertices must be connected if it has more than [(𝑛 − 1)(𝑛 −
2)]/2 edges.
(𝑛−𝑘)(𝑛−𝑘+1)
5. Prove that a simple graph with 𝑛 vertices and 𝑘 components can not have more than edges.
2
6. Define an r-regular graph on n vertices and draw the 4-regular graph on 6 vertices.
7. If a graph G has more than two vertices of odd degree, then prove that there can be no Euler path in G.
8.
9. Draw a connected graph that becomes disconnected when any edge is removed from it.
10. Observe that there can be no path longer than a Hamiltonian path (if it exists) in a graph and also draw
a graph that has a Hamiltonian path but does not have Hamiltonian circuit.
11. Draw a graph which has an Eulerian circuit but not a Hamiltonian circuit.
12. Suppose a graph G contains two distinct paths from a vertex u to a vertex v. Show that G has a cycle.
13. Is there a non-empty simple graph with twice as many edges as vertices?
14. Does there exists a simple graph with seven vertices having degrees (1, 3, 3, 4, 5, 6, 6)?
15. Determine whether the following pairs of graphs are isomorphic.
(i) 𝐾3 and a triangle (ii) 𝐾4 and a rectangle (iii) 𝐾5 and a 4-regular graph on 5 vertices.
16. Construct a graph G with the following properties: Edge connectivity of G=4, vertex connectivity of
G=3 and degree of every vertex of G≥5.
17. Is every regular graph of degree d (d≥3) non-separable? If not, give a simple regular graph of degree
three that is separable.
18. Prove that the edge connectivity of a graph G cannot exceed the minimum degree of a vertex in G.
19. Let G be a finite connected planar graph with at least three vertices. Show that G has at least one vertex
of degree 5 or less.
20. Prove that an Euler graph cannot have a cut-set with an odd number of edges.
21. If every region of a simple planar graph (with n vertices and e edges) embedded in a plane is bounded
k(n−2)
by k edges, show that e= .
k−2
22. Construct an example to demonstrate that G**, the dual of dual of a graph G, may not be isomorphic
of G, but is 2-isomorphic to it.
23. Show by sketching, that the thickness of the eight-vertex complete graph is two, whereas that of the
nine vertex complete graph is three.
24. Show that a set of fundamental circuits in a planar graph G corresponds to a set of fundamental cut sets
in its dual G*.
𝑛2
25. Show that the number of edges in a bipartite graph with n vertices is at most .
4
26. Prove that the chromatic number of a graph will not exceed by more than one the maximum degree of
the vertices in a graph.
27. Draw all the trees with six vertices.
28. Prove that a tree with n vertices has (n – 1) edges.
29. Prove that a graph G is a tree iff G has no cycles and │E│ =│ V│ −1.
30. Prove that a simple graph is connected if and only if it has a spanning tree.
31. How many edges are there in an undirected graph with two vertices of degree 7, four vertices of degree
5, and the remaining four vertices of degree 6?
32. Find three spanning tree for the following graph given below

33. Draw all spanning trees of the following graph given below

34. Use Prim Alogorithms to find a minimum spanning tree for the given weighted graph

35. Use Kruskal’s algorithms to find a minimum spanning tree for the given weighted graph

36. Obtain the incidence and the adjacency matrix of the graph

37. Apply Dijkstra’s algorithm to find out the shortest path from the vertices 𝑎 to 𝑒 in the following graph
38. Show that every tree with two or more vertices is 2-chromatic.
39. Show that the chromatic polynomial of a graph of n vertices satisfies the inequality𝑃(𝜆) ≤
𝜆(𝜆 − 1)𝑛−1 .
40. Prove that a graph of n vertices is a tree if and only if its chromatic polynomial is 𝑃𝑛 (𝜆) = 𝜆(𝜆 − 1)𝑛−1 .
41. Sketch two different graphs (non isomorphic) that have same chromatic polynomial.
42. In a village there are an equal number of boys and girls of marriageable age. Each boy dates as certain
number of girls and each girl dates a certain number of boys. Under what condition is it possible that
every boy and girl gets married to one of their dates? (Polygamy and polyandry not allowed.)
43. Sketch a graph with an even number of vertices that has no dimer covering.
44. Explore how the covering number of a graph G with n vertices is related to the diameters of G.
45. Show that the regions of a simple planar graph G can be colored properly with two colors if and only
if every vertex in G is of even degree.