Instructions
- Questions 1 to 10 ask for a True or False answer with a short justification.
- Questions 11 to 17 ask for short proofs of standard graph-theoretic facts.
- Worked solutions are provided immediately below each question.
- Use standard definitions of path, trail, cycle, tree, clique, chromatic number, Eulerian cycle, and Hamiltonian cycle.
Part A: True or False
Give a one-line reason with each answer. A correct truth value without justification should not receive full credit.
Q1
Clique Number and Chromatic Number
For every graph \(G\), the size of the largest clique is at most the chromatic number: \[ \omega(G) \le \chi(G). \]
Solution: True. All vertices in a clique are pairwise adjacent, so they must receive distinct colors in any proper coloring. Hence a clique of size \(\omega(G)\) forces at least \(\omega(G)\) colors, and therefore \(\omega(G) \le \chi(G)\).
Q2
Chromatic Number and Number of Vertices
If a graph \(G\) has \(n\) vertices, then \[ \chi(G) \le n. \]
Solution: True. We can always assign a different color to each of the \(n\) vertices, so every graph on \(n\) vertices is properly colorable with at most \(n\) colors.
Q3
Chromatic Number Need Not Equal Clique Number
If \(\chi(G)=3\), then \(G\) must contain a clique of size 3.
Solution: False. The cycle \(C_5\) has chromatic number \(3\), but its largest clique has size \(2\). So \(\chi(G)=3\) does not force a triangle.
Q4
Bipartite Graphs and Coloring
Every bipartite graph with at least one edge has chromatic number 2.
Solution: True. A bipartite graph is 2-colorable by coloring the two parts with two colors, and the presence of at least one edge means the graph cannot be colored with only one color.
Q5
Trees Are Bipartite
Every tree is a bipartite graph.
Solution: True. A tree has no cycles, hence no odd cycles. A graph is bipartite exactly when it has no odd cycle, so every tree is bipartite.
Q6
Odd Cycles
Every odd cycle is bipartite.
Solution: False. Odd cycles are the standard obstruction to bipartiteness. For example, \(C_3\) and \(C_5\) are not bipartite.
Q7
Edge Count in Trees
Every tree on \(n\) vertices has exactly \(n-1\) edges.
Solution: True. This is a basic theorem on trees: every connected acyclic graph with \(n\) vertices has exactly \(n-1\) edges.
Q8
Connected Graphs with \(n-1\) Edges
Every connected graph on \(n\) vertices with exactly \(n-1\) edges is a tree.
Solution: True. If a connected graph with \(n-1\) edges had a cycle, we could remove one edge from that cycle and the graph would stay connected, giving a connected graph on \(n\) vertices with only \(n-2\) edges, which is impossible. So it is connected and acyclic, hence a tree.
Q9
Adjacency Matrix Symmetry
For every simple undirected graph \(G\), the adjacency matrix of \(G\) is symmetric.
Solution: True. In an undirected graph, \(u\) is adjacent to \(v\) exactly when \(v\) is adjacent to \(u\). Therefore \(A_{uv}=A_{vu}\), so the adjacency matrix is symmetric.
Q10
Row Sums in the Adjacency Matrix
In a simple undirected graph, the sum of the entries in the row corresponding to a vertex \(v\) in the adjacency matrix equals \(\deg(v)\).
Solution: True. In a simple graph, the row for \(v\) has a \(1\) exactly in the columns corresponding to neighbors of \(v\), so the row sum counts the number of neighbors of \(v\), namely \(\deg(v)\).
Part B: Proof Questions
These questions ask for short proofs of standard facts about Eulerian cycles, Hamiltonian cycles, bridges, and graph distance.
Q11
Even Degrees in Eulerian Graphs
Prove that if a connected graph has an Eulerian cycle, then every vertex of the graph has even degree.
Solution: Let \(C\) be an Eulerian cycle of the graph. Each time the traversal arrives at a vertex by some edge, it must leave that vertex by a different unused edge, so the incident edges at that vertex are used in enter-leave pairs. The starting vertex is also the ending vertex, so its first departure is paired with the final arrival. Thus all edges incident to every vertex can be grouped into pairs, which means every vertex has even degree.
Q12
Odd-Degree Endpoints of an Eulerian Trail
Prove that if a connected graph has an Eulerian trail that is not a cycle, then the graph has exactly two vertices of odd degree.
Solution: Let the Eulerian trail start at \(s\) and end at \(t\), where \(s \ne t\) because the trail is not a cycle. For every vertex different from \(s\) and \(t\), each time the trail enters that vertex it must later leave it, so the used incident edges come in pairs and its degree is even. At \(s\), the trail has one extra departure and no matching final return, so \(\deg(s)\) is odd. At \(t\), the trail has one extra arrival, so \(\deg(t)\) is odd. Hence exactly two vertices, namely \(s\) and \(t\), have odd degree.
Q13
Distance Decomposition Along a Shortest Path
Prove that if \(d(u,v)\ge 2\), then there is a vertex \(z\) in \(G\) such that \[ d(u,v)=d(u,z)+d(z,v). \]
Solution: Let
\[
u=x_0,x_1,\dots,x_k=v
\]
be a shortest \(u\)-\(v\) path. Then \(k=d(u,v)\) and \(k \ge 2\). Choose \(z=x_1\), the first internal vertex on this shortest path. Clearly \(d(u,z)=1\). Also, the subpath
\[
z=x_1,x_2,\dots,x_k=v
\]
has length \(k-1\), so \(d(z,v) \le k-1\). If \(d(z,v) < k-1\), then combining a shorter \(z\)-\(v\) path with the edge \(ux_1\) would give a \(u\)-\(v\) path shorter than \(k\), contradicting the choice of the path. Hence \(d(z,v)=k-1\). Therefore
\[
d(u,z)+d(z,v)=1+(k-1)=k=d(u,v).
\]
Q14
Minimum Degree in a Hamiltonian Graph
Prove that if a graph has a Hamiltonian cycle, then every vertex has degree at least 2.
Solution: Suppose \(G\) has a Hamiltonian cycle \(C\). Every vertex of \(G\) appears exactly once on \(C\), and on the cycle each vertex is incident with two distinct cycle edges: one by which the cycle enters the vertex and one by which it leaves. These two edges are edges of \(G\), so every vertex has degree at least \(2\).
Q15
Bipartite Hamiltonian Graphs
Prove that if a bipartite graph has a Hamiltonian cycle, then the two parts of the bipartition have the same number of vertices.
Solution: Let the bipartition be \(V(G)=X \cup Y\), where every edge joins a vertex of \(X\) to a vertex of \(Y\). If \(G\) has a Hamiltonian cycle, then as we move around that cycle the vertices must alternate between \(X\) and \(Y\), because consecutive vertices on the cycle are adjacent. Therefore the cycle contains equally many vertices from \(X\) and \(Y\). Since the cycle is Hamiltonian, it visits every vertex of \(G\) exactly once. Hence \(|X|=|Y|\).
Q16
Every Edge Is a Bridge
Prove that if every edge of a connected graph is a bridge, then the graph is a tree.
Solution: Let \(G\) be connected and suppose every edge of \(G\) is a bridge. We claim that \(G\) has no cycle. If there were a cycle, then removing any one edge from that cycle would still leave a path between its endpoints using the rest of the cycle, so that edge would not disconnect the graph. This contradicts the assumption that every edge is a bridge. Thus \(G\) is acyclic. Since \(G\) is both connected and acyclic, \(G\) is a tree.
Q17
Characterizing Bridges by Cycles
Prove that an edge of a graph is a bridge if and only if it does not belong to any cycle.
Solution: Let \(e=uv\) be an edge.
First suppose \(e\) is a bridge. If \(e\) belonged to a cycle, then the rest of that cycle would give a \(u\)-\(v\) path even after deleting \(e\). So removing \(e\) would not disconnect the graph, contradicting that \(e\) is a bridge. Hence a bridge cannot lie on any cycle.
Conversely, suppose \(e\) does not belong to any cycle. If \(e\) were not a bridge, then after deleting \(e\) there would still be a path from \(u\) to \(v\). Together with the edge \(e\), that path would form a cycle containing \(e\), which is impossible. Therefore \(e\) must be a bridge.
Thus an edge is a bridge if and only if it does not belong to any cycle.
First suppose \(e\) is a bridge. If \(e\) belonged to a cycle, then the rest of that cycle would give a \(u\)-\(v\) path even after deleting \(e\). So removing \(e\) would not disconnect the graph, contradicting that \(e\) is a bridge. Hence a bridge cannot lie on any cycle.
Conversely, suppose \(e\) does not belong to any cycle. If \(e\) were not a bridge, then after deleting \(e\) there would still be a path from \(u\) to \(v\). Together with the edge \(e\), that path would form a cycle containing \(e\), which is impossible. Therefore \(e\) must be a bridge.
Thus an edge is a bridge if and only if it does not belong to any cycle.