Question Bank (Module-4)
Degree & Handshaking Lemma
1. Prove that in any simple graph with at least two vertices, there are two vertices having the
same degree.
2. A simple graph has 15 vertices and 40 edges. Show that at least one vertex has degree ≥
6.
4. Prove that the number of vertices of odd degree in any graph is always even.
Paths, Walks, and Cycles
1. Prove that every walk between two vertices contains a path between those vertices.
2. Let G be a graph in which every vertex has degree ≥ 2. Prove that G contains a cycle.
3. Show that a connected graph with n vertices and n−1 edges is a tree.
4. Prove or disprove: If a graph has exactly one simple path between every pair of vertices,
then it is a tree.
Connectedness
1. Let G be a disconnected graph with n vertices and m edges. Prove that m ≤ (n−1)(n−2)/2.
2. Show that removing an edge from a connected graph either keeps it connected or
increases the number of components by exactly one.
Complete Graphs & Special Graphs
1. Prove that the complete graph K_n has n(n−1)/2 edges.
2. How many edges must be removed from K_n to obtain a tree? Prove your answer.
3. Determine whether a graph with 7 vertices each of degree 3 exists. Justify.
Bipartite Graphs
1. Prove that a graph is bipartite if and only if it contains no odd cycle.
2. Show that every tree is bipartite.
3. Prove that a complete graph K_n is bipartite only when n ≤ 2.
Graph Isomorphism
1. Determine whether the following degree sequences can correspond to isomorphic
graphs:
G1: (3,3,2,2,2,1,1)
G2: (3,3,3,2,2,1,0).
2. Give two non-isomorphic graphs having the same number of vertices, number of edges,
and degree sequence. Explain why they are not isomorphic.
Advanced Conceptual Problems
1. Prove that every graph contains a path of length at least equal to its minimum degree.
2. Let G be a simple graph with n vertices. Prove that either G or its complement is
connected.
Proof-Intensive Problems
1. Show that a graph with average degree greater than 2k−2 must contain a cycle of length
at least k.
2. Prove that every finite graph has an even number of vertices of odd degree using
induction on edges.
Basic Properties of Trees
2. Show that every tree with at least two vertices has at least two pendant (degree 1)
vertices.
3. Let T be a tree with maximum degree Δ. Prove that T has at least Δ leaves.
4. Prove that adding any edge to a tree creates exactly one cycle.
5. Show that removing any edge from a tree disconnects the graph.
Characterizations of Trees (Conceptual)
1. Prove that the following are equivalent for a graph G:
1. G is a tree
2. G is connected and acyclic
3. There is a unique path between every pair of vertices
4. G has n−1 edges and is connected.
2. Prove that a connected graph is a tree if and only if every edge is a bridge.
3. Show that a graph without cycles is a forest.
Cycles — Advanced Problems
1. Prove that every graph with minimum degree ≥ 2 contains a cycle.
2. Show that a graph contains an even cycle if it is bipartite and contains any cycle.
3. Prove that a tree cannot contain a cycle using contradiction.
4. Let G be a graph with n vertices and more than n−1 edges. Prove that G must contain a
cycle.
Proof-Intensive (Exam Level)
1. Prove that every longest path in a tree starts and ends at pendant vertices.
2. Show that the center of a tree is either one vertex or two adjacent vertices.
3. Prove that any two vertices in a tree are connected by exactly one simple path.
Challenging Conceptual Problems
1. If all vertices of a graph have even degree, prove that every edge lies on a cycle or is part
of a cycle component.
2. Show that a tree with n vertices has at most n−2 vertices of degree greater than 1.
Eulerian/Hamiltonian
1. Define Eulerian path and Eulerian circuit with examples.
2. State necessary and sufficient conditions for a graph to have an Eulerian circuit.
3. Define Hamiltonian path and Hamiltonian cycle.
4. Give an example of a graph that is Eulerian but not Hamiltonian.
5. Give an example of a graph that is Hamiltonian but not Eulerian.
6. What is the difference between Eulerian and Hamiltonian graphs?
7. Explain why a graph with exactly two vertices of odd degree has an Eulerian path.
8. Prove that a connected graph is Eulerian if and only if every vertex has even degree.
9. Check whether K_5 and K_6 are Eulerian and/or Hamiltonian.
10. Determine Eulerian and Hamiltonian properties of cycle graph C_n and path graph P_n.
11. Give an example of a graph that is neither Eulerian nor Hamiltonian.
12. Construct a graph that has an Eulerian path but no Hamiltonian cycle.
13. Show that removing an edge from an Eulerian graph may destroy its Eulerian property.
14. For what values of n is the complete bipartite graph K_{m,n} Eulerian or Hamiltonian?
15. Consider a graph with vertices {A, B, C, D} and edges {AB, BC, CD, DA, AC}. Determine
whether it has an Eulerian path or circuit. Also check if it has a Hamiltonian cycle.
16. A graph has vertices {1,2,3,4,5} and edges {12, 23, 34, 45, 51, 13}. Determine whether
the graph is Eulerian. Find a Hamiltonian cycle if it exists.
17. Consider a graph with vertices {P, Q, R, S, T} and edges {PQ, QR, RS, ST, TP, PR}.
Determine whether it contains (i) Eulerian circuit, (ii) Hamiltonian path.
18. Given a graph with vertices {A, B, C, D, E} and edges {AB, AC, AD, AE}. Determine
whether it has an Eulerian path. Does it contain a Hamiltonian path?
19. Consider the complete graph K5. Determine whether it is Eulerian and Hamiltonian.
Find an Eulerian circuit and a Hamiltonian cycle.
20. Consider the cycle graph C6. Does it have an Eulerian circuit? Is it Hamiltonian? Justify
your answer.
21. A graph has vertices {1,2,3,4,5,6} and edges {12, 23, 34, 45, 56, 61, 13, 35}. Determine
Eulerian and Hamiltonian properties.
22. Consider a graph with vertices {A, B, C, D} and edges {AB, BC, CD}. Determine whether
it has an Eulerian path or circuit. Check Hamiltonian path.