CS 637: Mathematics-II

1. A connected graph $G$ represents a network. When a vertex $v$ is removed, $G-v$ has three connected components of sizes $4, 5,$ and $7$. Apply the cut-vertex characterization (a vertex is a cut vertex exactly when removing it increases the number of connected components) to explain why $v$ is an articulation point and identify the natural partition of $G-v$.

2. A connected graph has exactly two vertices whose removal does not disconnect the graph. Apply the characterization that a connected graph with exactly two non-cut vertices must be a path to decide the structure of $G$, and draw one example on $6$ vertices.

3. A connected graph $G$ represents a network and has $18$ vertices and $18$ edges. Use the unicyclic-graph theorem (a connected graph with $n$ vertices and $n$ edges has exactly one cycle) to determine how many cycles $G$ contains. What changes if a graph with the same numbers of vertices and edges is disconnected?

4. Let $T$ be a tree on $15$ vertices. Apply the centroid theorem for trees (every tree has either one centroid or two adjacent centroids, where deleting a centroid leaves no component with more than half the vertices) to identify what kind of vertex, or pair of adjacent vertices, can be chosen so that the remaining components are balanced.

5. A tree has internal vertex degrees $4,3,3,2,2$. Apply the leaf-count identity for trees ($\sum_{v:\deg(v)\geq 2}(\deg(v)-2)=\ell-2$, where $\ell$ is the number of leaves) to determine the number of leaves and the total number of vertices.

6. Use the degree-sum theorem for trees (a tree on $n$ vertices has degree sum $2(n-1)$) to test whether a tree with $12$ vertices can have exactly $5$ leaves and $7$ vertices of degree at least $2$. If it is possible, give one construction; if not, explain which count fails.

7. In a tree $T$, define one pruning round as the deletion of all current leaves. Apply the pruning behavior of trees (repeatedly deleting leaves eventually leaves either one vertex or one edge) to the path $P_{11}$ and the star $K_{1,10}$. How many rounds are needed in each case?

8. A finite tree has maximum degree $\Delta=3$. Apply the embedding theorem for trees (any tree with maximum degree at most $\Delta$ can be embedded in the infinite $\Delta$-regular tree) to place it inside the infinite $3$-regular tree. Use this viewpoint to estimate how many vertices can lie within distance $r$ of a chosen root.

9. A connected graph has $10$ vertices and every vertex has degree $2$. Apply the classification of connected $2$-regular graphs (every connected $2$-regular graph is a cycle) to identify the graph. If the graph is not connected and has $10$ vertices, list two possible component decompositions.

10. A simple graph has $12$ vertices and minimum degree $6$. Apply Dirac's theorem (if $n\geq 3$ and $\delta(G)\geq n/2$, then $G$ is Hamiltonian) to decide whether it must contain a Hamiltonian cycle. Then compare this with a graph on $12$ vertices with minimum degree $5$.

11. For graphs on $9, 10,$ and $11$ vertices, compute the minimum-degree threshold that guarantees a Hamiltonian path by the Hamiltonian-path corollary of Dirac's theorem (if $\delta(G)\geq (n-1)/2$, then $G$ has a Hamiltonian path). Give one example where the path guarantee applies but Dirac's cycle guarantee does not.

12. A matching $M$ in a graph leaves two unmatched vertices connected by an $M$-augmenting path of length $5$. Apply Berge's augmenting-path theorem (a matching is maximum if and only if there is no augmenting path) to decide whether $M$ is maximum, and describe how to improve it.

13. A bipartite graph has parts $X=\{a,b,c,d\}$ and $Y=\{1,2,3,4\}$ with neighborhoods $N(a)=\{1,2\}$, $N(b)=\{1,2\}$, $N(c)=\{2,3,4\}$, and $N(d)=\{3,4\}$. Apply Hall's theorem (there is a matching saturating $X$ if and only if $|N(S)|\geq |S|$ for every $S\subseteq X$) to decide whether there is a matching that saturates $X$.

14. A bipartite graph with $|X|=|Y|=6$ has a matching of size $5$ but no perfect matching. Use Hall's theorem (there is a perfect matching saturating $X$ if and only if $|N(S)|\geq |S|$ for every $S\subseteq X$) to find what kind of subset $S\subseteq X$ must witness the failure, and construct one example.

15. Apply the formula for matchings in a path (the number of matchings of size $k$ in $P_n$ is $\binom{n-k}{k}$) to compute the number of matchings of size $3$ in $P_8$. Interpret the same count as choosing $3$ non-adjacent edges from a line of $7$ edges.

16. A connected graph has a unique perfect matching. Apply the bridge theorem for unique perfect matchings (every connected graph with a unique perfect matching contains a bridge that belongs to the matching) to identify a structural feature that must be present. Give an example showing why the converse should be checked carefully.

17. A graph has $20$ vertices and independence number $\alpha(G)=8$. Apply Gallai's identity ($\alpha(G)+\tau(G)=|V(G)|$) to determine the minimum vertex-cover size $\tau(G)$. Explain how a maximum independent set gives a minimum vertex cover in this case.

18. In a bipartite graph, a maximum matching has size $7$. Apply Konig's theorem (in a bipartite graph, the maximum matching size equals the minimum vertex-cover size) to determine the size of a minimum vertex cover. Compare with the triangle $K_3$ to see what can fail outside bipartite graphs.

19. Given a bipartite graph and a maximum matching $M$, apply the standard alternating-path construction from Konig's theorem (in a bipartite graph, the maximum matching size equals the minimum vertex-cover size) to find a minimum vertex cover. Work it out on the graph with $U=\{u_1,u_2,u_3\}$, $V=\{v_1,v_2,v_3\}$ and edges $u_1v_1,u_1v_2,u_2v_2,u_3v_2,u_3v_3$.

20. Apply the formula for domination in complete bipartite graphs ($\gamma(K_{m,n})=1$ if $\min\{m,n\}=1$, and $\gamma(K_{m,n})=2$ otherwise) to compute $\gamma(K_{1,8})$, $\gamma(K_{2,5})$, and $\gamma(K_{4,4})$. In each case, describe a minimum dominating set.

21. A graph has $n=30$ vertices and minimum degree $4$. Apply the domination bound in terms of minimum degree ($\gamma(G)\leq n/(\delta(G)+1)$) to estimate how small a dominating set is guaranteed to be. Give a graph family where this estimate is attained exactly.

22. For a graph without isolated vertices, suppose $\gamma(G)=5$. Apply the standard inequality between domination and total domination ($\gamma(G)\leq \gamma_t(G)\leq 2\gamma(G)$) to bound $\gamma_t(G)$. Give an example where the upper bound is close to the truth.

23. A graph contains a subdivision of $K_{3,3}$ as a subgraph. Apply Kuratowski/Wagner-type planarity criteria (a graph is planar exactly when it has no subdivision/minor obstruction of type $K_5$ or $K_{3,3}$) to decide whether the graph can be planar. Then check whether the same reasoning applies to a graph containing a $K_5$ minor.

24. A simple connected planar graph has $n=14$ vertices. Apply Euler's formula ($n-m+f=2$) and the planar edge bound ($m\leq 3n-6$ for simple planar graphs with $n\geq 3$) to find the maximum possible number of edges. Can such a graph have $38$ edges?

25. A simple planar graph is being colored greedily by repeatedly deleting a low-degree vertex. Apply the fact that every planar graph has a vertex of degree at most $5$ to explain why this strategy supports a $6$-coloring. What extra idea is needed to reach $5$ colors?

26. A connected plane graph has $8$ faces. Apply planar duality (vertices of $G^*$ correspond to faces of $G$, and edges cross corresponding primal edges) to determine the number of vertices of $G^*$. If an edge $e$ is a bridge in $G$, describe what happens to the corresponding edge $e^*$ in the dual.

27. A planar graph has been drawn with curved edges and no crossings. Apply Fary's theorem (every simple planar graph has a crossing-free straight-line drawing) to decide whether it can be redrawn with straight-line edges and no crossings. What does this say about planar embeddings?

28. A planar graph has $n=100$ vertices. Apply the grid-embedding theorem (every planar graph on $n$ vertices has a crossing-free drawing on an $O(n)\times O(n)$ grid) to estimate the order of grid size sufficient for a crossing-free drawing. What does this imply about representing planar embeddings with integer coordinates?

29. A planar graph has $n=10{,}000$ vertices. Apply the planar separator theorem (every planar graph on $n$ vertices has a separator of size $O(\sqrt n)$ whose removal leaves components of size at most a fixed fraction of $n$) to estimate the size of a separator guaranteed by the $4\sqrt{n}$ bound. What is the largest allowed size of each remaining component after removal?

30. Suppose an exponential-time algorithm for a graph problem branches only on a planar separator. Apply the planar separator theorem (every planar graph has a separator of size $O(\sqrt n)$ that splits the graph into smaller parts) to explain why the resulting running time can be subexponential in $n$ for planar graphs. How does this differ from arbitrary graphs?