Source
Filtered from West plus course questions
Question Count
35 lecture-aligned questions
Coverage
Foundations, degree sequences, trees, spectra, Hamiltonicity, matchings
Study Note
- This sheet keeps only those West-style questions that match the graph theory material covered in the lectures.
- The first part is a filtered West-based bank, and the second part adds course-specific practice problems.
- Try writing complete arguments, not just final answers.
Filtered West Questions Covered in the Lectures
Chapter 1: Fundamental Concepts
- Define a simple graph. What distinguishes it from a multigraph and a pseudograph?
- Let \(G\) be a graph with vertex set \(V = \{1, 2, 3, 4, 5\}\) and edge set \(E = \{12, 13, 24, 35, 45\}\). Draw \(G\), write its adjacency matrix, and determine whether \(G\) is bipartite.
- The Petersen graph has 10 vertices and 15 edges. Verify that it is 3-regular and has girth 5.
- Define the complete bipartite graph \(K_{m,n}\). How many edges does \(K_{m,n}\) have? For which values of \(m, n\) is \(K_{m,n}\) a regular graph?
- Prove that \(K_n\) has \(\binom{n}{2}\) edges and is \((n-1)\)-regular.
- A graph \(G\) has adjacency matrix \(A\). What does the \((i,j)\)-entry of \(A^2\) count? Prove your answer.
- Prove that every closed odd walk in a graph contains an odd cycle.
- Let \(G\) be a graph. Prove that \(G\) is bipartite if and only if it contains no odd cycle.
- Show that in any graph \(G\), the number of vertices of odd degree is even.
- State and prove the Handshaking Lemma:
\[ \sum_{v \in V(G)} d(v) = 2|E(G)|. \]
- A sequence \((d_1, d_2, \ldots, d_n)\) of non-negative integers is graphic if it is the degree sequence of some simple graph. Use the Erdős-Gallai theorem to determine whether \((5, 4, 3, 3, 2, 2, 1)\) is graphic.
- A \(k\)-regular bipartite graph with parts \(X\) and \(Y\) satisfies \(|X| = |Y|\). Prove this using degree counting.
Chapter 3: Matchings and Factors
- State and prove Hall's Marriage Theorem: a bipartite graph \(G\) with parts \(X\) and \(Y\) has a matching that saturates \(X\) if and only if \(|N(S)| \geq |S|\) for every \(S \subseteq X\).
- Define a maximum matching, a perfect matching, and a maximal matching. Give an example showing that a maximal matching need not be maximum.
- Prove that every \(k\)-regular bipartite graph, where \(k \geq 1\), has a perfect matching, using Hall's theorem.
Additional Course-Based Practice
Questions 16-35 Based on the Course Graph Theory Lectures
- Define each of the following terms: graph, path, cycle, clique, bipartite graph, cut vertex, and bridge.
- Let \(G\) have vertex set \(V=\{v_1,v_2,v_3,v_4\}\) and edge set
\[ E=\{v_1v_2,\; v_1v_3,\; v_2v_4,\; v_3v_4\}. \]Write the adjacency matrix and the degree of each vertex.
- For the same graph as in Question 17, write one possible incidence matrix. State clearly the order of the vertices and edges that you use.
- Prove that every connected graph contains a spanning tree.
- Let \(G\) be a simple graph with minimum degree at least \(2\). Prove that \(G\) contains a cycle.
- Prove that every tree on \(n\) vertices has exactly \(n-1\) edges. Then prove the converse: every connected graph on \(n\) vertices with \(n-1\) edges is a tree.
- State two immediate necessary conditions for a nonnegative integer sequence
\[ d_1 \ge d_2 \ge \cdots \ge d_n \]to be graphical. Give one example of a sequence satisfying these necessary conditions but still not graphical.
- Use the Havel-Hakimi process to determine whether the sequence
\[ (4,3,3,2,2,2) \]is graphical. If it is graphical, construct one realizing graph.
- Let \(A\) be the adjacency matrix of a simple undirected graph \(G\) with eigenvalues \(\lambda_1,\dots,\lambda_n\). Prove that
\[ \sum_{i=1}^n \lambda_i = 0 \qquad \text{and} \qquad \sum_{i=1}^n \lambda_i^2 = 2|E(G)|. \]
- State the meaning of the \((i,j)\)-entry of \(A^k\). Then explain how this fact can be used to test whether there is a walk of length \(k\) from \(v_i\) to \(v_j\).
- Prove that the path graph \(P_n\) with \(n \ge 2\) has exactly two non-cut vertices.
- Prove that a connected graph with \(n\) vertices and \(n\) edges has exactly one cycle.
- Let \(T\) be a tree with \(n\) vertices. Suppose \(T\) has \(n-k+1\) leaves and exactly one vertex of each degree \(2,3,\dots,k\). Find the relation between \(n\) and \(k\).
- Prove by induction that every finite connected simple graph in which each vertex has degree \(2\) is a cycle.
- Prove the same statement as in Question 29 by contradiction using a minimal counterexample and suppression of a degree-\(2\) vertex.
- State Dirac's theorem. Then prove it using a maximum non-Hamiltonian graph. Your proof should explain clearly why the contradiction arises.
- For each of the following values of \(n\), determine the minimum degree threshold given by Dirac's theorem and explain what conclusion it gives about Hamiltonicity:
\[ n=6,\qquad n=7,\qquad n=10. \]
- Define an augmenting path with respect to a matching \(M\). Show that if a graph contains an augmenting path relative to \(M\), then \(M\) is not a maximum matching.
- Consider the bipartite graph \(G=(X \cup Y,E)\), where
\[ X=\{x_1,x_2,x_3,x_4\}, \qquad Y=\{y_1,y_2,y_3,y_4,y_5\}, \] \[ N(x_1)=\{y_1,y_2\},\quad N(x_2)=\{y_2,y_3\},\quad N(x_3)=\{y_3,y_4\},\quad N(x_4)=\{y_1,y_4,y_5\}. \]Check Hall's condition for subsets of \(X\), and determine whether there exists a matching saturating all vertices of \(X\).
- Let \(M\) be a maximal matching in a graph \(G\). Prove that the set of all endpoints of edges in \(M\) forms a vertex cover of \(G\). Deduce that \(G\) has a vertex cover of size at most \(2|M|\).
Tips for Study
- Questions 1 to 15 are the West-based questions that best match the lecture coverage.
- Questions 16 to 35 are course-specific practice questions based directly on Lectures 18 to 21.
- For revision, start with definitions and counting, then move to structural proofs, Dirac's theorem, and Hall's theorem.