Exercises: Introduction to Graphs

DataField.Dev

Exercises: Introduction to Graphs

These run from mechanical warm-ups through proofs, code, modeling, and a section that interleaves earlier chapters. Difficulty: ⭐ foundational, ⭐⭐ intermediate, ⭐⭐⭐ challenging. Worked solutions to the daggered (†) and odd-numbered problems are in the appendix answers-to-selected.md — draw the graph and try the problem before you peek. Every theorem in this chapter started as someone drawing dots and lines, so keep a pencil moving.

Unless a problem says otherwise, "graph" means a simple graph (no loops, no parallel edges), exactly as in §27.1.

Part A — Warm-ups (⭐)

27.1 † Write $V$ and $E$ as explicit sets for the following graph: four vertices $p, q, r, s$ with edges joining $p$–$q$, $q$–$r$, $r$–$s$, and $s$–$p$. How many edges does it have, and what is $\deg(q)$?

27.2 For the study-group graph of §27.1 ($V=\{$Ana, Ben, Cam, Dev, Eve$\}$ with the five friendships), list $N(\text{Dev})$ and compute $\deg(\text{Dev})$.

27.3 † A simple graph has 6 vertices. What is the largest number of edges it can possibly have? State the formula you used and evaluate it.

27.4 Give the degree sequence (the multiset of all degrees, written in non-increasing order) of the complete graph $K_4$. What is $\deg(v)$ for every vertex of $K_n$?

27.5 † In the "follows" digraph of §27.3 (Ana→Ben, Ben→Cam, Cam→Ana, Cam→Ben), compute $\deg^+(\text{Cam})$, $\deg^-(\text{Cam})$, and $\deg^-(\text{Ben})$.

27.6 Classify each as directed or undirected, and say why in one phrase: (a) "is married to"; (b) "is the manager of"; (c) "shares a wall with" (between rooms); (d) "imports the module" (between Python files).

Part B — Computation (⭐⭐)

27.7 † A graph has degree sequence $(5, 3, 3, 2, 2, 1)$. How many edges does it have? Use the handshaking lemma and show the arithmetic.

27.8 How many edges are in the complete bipartite graph $K_{4,6}$? How many are in $K_{10}$? Which is larger, and by how much?

27.9 † List every distinct path from Ana to Eve in the study-group graph (no repeated vertices). For each, give its length. Which is shortest?

27.10 A graph on the vertex set $\{1,2,3,4,5,6\}$ has edge set $E = \{\{1,2\},\{2,3\},\{4,5\}\}$. Is it connected? If not, list its connected components, and state how many isolated vertices it has.

27.11 † Decide whether each degree sequence is possible for a simple graph, using the even-degree-count corollary. If a sequence is ruled out, say why. (a) $(3,3,3,3)$; (b) $(4,4,4,2,1)$; (c) $(1,1,1,1)$; (d) $(3,2,2,2,1)$.

27.12 The 4-cycle (a square) and the complete graph $K_4$ both have 4 vertices. Give the degree sequence of each and the number of edges of each, and state one cheap invariant that proves they are not isomorphic.

Part C — Prove it (⭐⭐, with scaffolding)

27.13 † (Scaffolded — fill the missing steps.) Prove that every graph has an even number of odd-degree vertices. Complete the blanks; this re-derives the §27.4 corollary in your own hand.

By the handshaking lemma, $\sum_{v \in V}\deg(v) = \underline{\hphantom{xxxx}}$, which is an even number.
Split the sum over $V_{\text{even}}=\{v:\deg(v)\text{ even}\}$ and $V_{\text{odd}}=\{v:\deg(v)\text{ odd}\}$: $\displaystyle\sum_{v\in V_{\text{even}}}\deg(v) + \sum_{v\in V_{\text{odd}}}\deg(v) = \underline{\hphantom{xxxx}}$.
The first sum is a sum of even numbers, so it is $\underline{\hphantom{xxxx}}$. Subtracting it from both sides, $\sum_{v\in V_{\text{odd}}}\deg(v)$ must also be $\underline{\hphantom{xxxx}}$.
A sum of $\lvert V_{\text{odd}}\rvert$ odd numbers is even if and only if $\lvert V_{\text{odd}}\rvert$ is $\underline{\hphantom{xxxx}}$. Therefore the number of odd-degree vertices is even. $\blacksquare$

27.14 Prove that in any graph with at least two vertices, there exist two distinct vertices of equal degree. (Hint: in a simple graph on $n$ vertices, each degree lies in $\{0, 1, \dots, n-1\}$, but degree $0$ and degree $n-1$ cannot both occur. Apply the pigeonhole principle — Chapter 17.)

27.15 † (Scaffolded.) Prove that a graph with $n$ vertices and more than $\binom{n}{2}$ edges cannot be simple. Fill the blanks.

In a simple graph each edge is a $\underline{\hphantom{xxxx}}$-element subset of $V$.
The number of such subsets of an $n$-element set is exactly $\underline{\hphantom{xxxx}}$.
A set $E$ of distinct edges can contain at most that many elements, so $\lvert E\rvert \le \underline{\hphantom{xxxx}}$.
Hence if $\lvert E\rvert > \binom{n}{2}$, two edges must coincide or some edge repeats a pair — i.e. the graph has $\underline{\hphantom{xxxxxxxx}}$ and is not simple. $\blacksquare$

27.16 Prove that the complete graph $K_n$ is connected for every $n \ge 1$. (One sentence using the definition of $K_n$ suffices — but write the sentence carefully, citing what guarantees a path between any two vertices.)

27.17 † Prove: if every vertex of a graph $G$ has degree at least 1, and $G$ has $n$ vertices, then $G$ has at least $\lceil n/2 \rceil$ edges. (Hint: sum the degrees and apply the handshaking lemma; $\sum \deg(v) \ge n$.)

Part D — Implement it (⭐⭐)

Write Python for each. Do not run it — hand-trace and include an # Expected output: comment, in the book's convention. You may build on the Graph class from the Project Checkpoint.

27.18 † Write a function degree_sequence(adj) that takes an adjacency dictionary (vertex → set of neighbors) and returns the sorted list of degrees. Test it by hand on the study-group adjacency dict and state what output confirms the handshaking lemma.

27.19 Write a function is_handshaking_ok(adj) that returns True exactly when the sum of degrees is even (equivalently, when the number of odd-degree vertices is even). Run it in your head on the adjacency dict $\{$"a": {"b","c"}, "b": {"a"}, "c": {"a"}$\}$ and report the output.

27.20 † Add a method common_neighbors(self, u, v) to the Graph class that returns the set $N(u) \cap N(v)$ — the mutual friends of $u$ and $v$. (This is the core of a "people you may know" suggester; see §27.6.) Show its output for common_neighbors("Ana", "Dev") on the study group.

27.21 Write complete_graph(n) that builds and returns a Graph equal to $K_n$ on vertices $0, 1, \dots, n-1$. Print num_edges() for complete_graph(5) and confirm it matches $\binom{5}{2}$.

Part E — Find the error (⭐⭐)

Each argument below is wrong. State precisely which step fails and why — then give the correct conclusion.

27.22 † Claim: "There is a simple graph on 5 vertices in which every vertex has degree 3." "Proof": "Each vertex needs 3 neighbors; with 5 vertices there is plenty of room, and we can just keep adding edges until every degree reaches 3, so such a graph exists." — Find the flaw. (Hint: compute $\sum \deg$ and apply a parity argument.)

27.23 Claim: "Two graphs with the same number of vertices and the same number of edges are isomorphic." "Proof": "An isomorphism is a bijection on vertices preserving edges; since both graphs have the same vertex count there is a bijection, and since they have the same edge count it maps edges to edges." — Find the flaw. Give a concrete 4-vertex counterexample with both graphs having exactly 3 edges.

27.24 † Claim: "If a graph is connected, then deleting any one edge leaves it connected." "Proof": "Connectivity means there is a path between every pair; removing a single edge still leaves all the other edges, so the paths are still there." — Find the flaw, and give the smallest graph where deleting one edge disconnects it. (Such an edge has a name from Chapter 30 — a bridge; you do not need that term to answer.)

27.25 Claim: "A bipartite graph cannot contain a triangle." A student writes: "A triangle has 3 vertices and 3 edges; put two of the vertices in $X$ and one in $Y$; then the edge between the two $X$-vertices stays inside $X$, contradicting bipartiteness — so no triangle." Their conclusion is correct, but one sentence of the reasoning is sloppy about why you cannot avoid an inside-$X$ edge. Tighten the argument by connecting it to the "no odd cycle" characterization (§27.3).

Part F — Model it & Conjecture and test (⭐⭐⭐)

27.26 † (Model it.) A university wants to detect scheduling conflicts: two exams cannot share a time slot if some student is enrolled in both. Model this as a graph. State explicitly: what is a vertex, what is an edge, is it directed or undirected, and what graph question corresponds to "what is the fewest number of time slots needed?" (You will not solve it — just translate. Name the chapter where this question is answered: it is graph coloring, Chapter 33.)

27.27 (Model it.) You are building a "people you may know" feature. Friendship is mutual. Specify the model in the four-question form from §27.6 (vertex? edge? directed/undirected? weighted?), then write a one-sentence precise specification of the suggestion in graph terms (use "distance 2" and "common neighbors"). Whom should the feature suggest to Eve in the study group, and why?

27.28 † (Conjecture and test, then prove.) For the complete graph $K_n$, conjecture a closed formula for the number of edges as a function of $n$ by computing it for $n = 1, 2, 3, 4, 5$ (do this by hand or with complete_graph(n).num_edges()). State your conjecture, then prove it from the definition of $K_n$. (This re-proves a fact from §27.1 — the point is to practice the conjecture-then-prove loop, Theme 4.)

27.29 (Conjecture and test, then prove or disprove.) Conjecture: "In every simple graph on $n \ge 2$ vertices, the number of vertices of even degree is at least one." Test it on several small graphs (try the path on 3 vertices, the triangle, the 4-cycle, and $K_4$). Do you find a counterexample? If the conjecture survives your tests, either prove it or explain why testing alone cannot settle it. (Hint: think about $K_4$ and about a single edge $K_2$.)

27.30 † (Conjecture and test.) Two graphs have the same degree sequence $(2,2,2,2,2,2)$. Build two non-isomorphic graphs with this degree sequence — one connected, one not — and explain, using an invariant other than degree sequence, why they cannot be isomorphic. What does this exercise prove about the degree-sequence test (§27.5)?

Part G — Interleaved & Deep Dive

Mixing earlier chapters keeps them sharp.

27.31 † (Ch. 8 + 27.) An undirected edge was stored as a frozenset of two vertices. Using the language of Chapter 8, explain exactly which set-theoretic object an edge is, and contrast it with the ordered pair used for a directed edge. Then state the size of the set of all possible edges of a simple graph on $V$ with $\lvert V\rvert = n$, as a count of subsets.

27.32 (Ch. 12 + 27.) "Reachable by a path" is an equivalence relation on the vertices of an undirected graph. Name the three equivalence-relation properties (Chapter 12) and, for each, give the one-line graph reason it holds. What are the equivalence classes called?

27.33 † (Ch. 12 + 27.) A directed graph is a relation drawn as a digraph. For the relation $R = \{(1,2),(2,1),(2,3),(3,3)\}$ on $\{1,2,3\}$, draw its digraph (describe it), give each vertex's in-degree and out-degree, and state whether $R$ is symmetric. If $R$ were symmetric, what kind of graph could you draw instead of a digraph?

27.34 (Ch. 16 + 27.) Count the number of distinct simple graphs on a fixed labeled vertex set $\{1, 2, 3\}$ (vertices are distinguishable; count by which edges are present). (Hint: there are $\binom{3}{2}$ possible edges, and each is independently present or absent — a power-set count from Chapters 8 and 16.) Generalize to $n$ labeled vertices.

27.35 (Ch. 17 + 27, Deep Dive.) Use the pigeonhole principle to prove the claim of Exercise 27.14 rigorously: in any simple graph on $n \ge 2$ vertices, two vertices have the same degree. Be careful about the "degree 0 and degree $n-1$ cannot coexist" subtlety — explain why that is what makes the pigeonhole argument close.

27.36 (Deep Dive.) Deciding graph isomorphism in general has no known efficient algorithm, yet "try all $n!$ relabelings" is hopeless. (a) Compute (order of magnitude) how many relabelings $n!$ is for $n = 12$. (b) Explain, in one paragraph, how an invariant such as the sorted degree sequence lets real systems (e.g. molecule or circuit comparison) avoid most of that search, and why a matching invariant still is not a proof of isomorphism. Connect to Theme 3 (abstraction is the master tool).

Solutions to † and odd-numbered exercises are in appendices/answers-to-selected.md. For each proof, the rubric rewards: a precisely stated claim, correct use of the handshaking lemma or the relevant definition, an explicit invariant where isomorphism is involved, and a clean conclusion ending in $\blacksquare$.