Day 21 — Graphs, Paths & Trees

Updated

July 30, 2025

Day 21 — Graphs, Paths & Trees

Day 59 — Graphs & handshaking

Stage VI · concept day
Goal: Define simple, multi, and directed graphs; prove the handshaking lemma; apply Havel–Hakimi to graphic sequences; recognize \(K_n\), \(C_n\), \(P_n\), \(K_{m,n}\); awareness of isomorphism.

Why this matters

Graphs model networks, dependencies, social links, call graphs, and state transitions. Degree and the handshaking lemma are the first global constraints: you cannot invent arbitrary degree lists. Everything in Stage VI builds on today’s vocabulary.

Theory

Undirected graph

An undirected graph \(G=(V,E)\) consists of a finite vertex set \(V\) and an edge set \(E\).

  • Simple graph: elements of \(E\) are 2-element subsets of \(V\) (no loops, no parallel edges).
  • Order \(n=|V|\), size \(m=|E|\).
  • Vertices \(u,v\) are adjacent if \(\{u,v\}\in E\); edge incident to its endpoints.
  • Neighbor set \(N(v)\); degree \(\deg(v)=|N(v)|\) in a simple graph.

Multigraphs allow parallel edges between the same pair; loops are edges with both ends the same vertex (a loop contributes \(2\) to degree). Unless stated, assume simple undirected graphs.

Directed graphs (digraphs)

\(G=(V,E)\) with \(E\subseteq V\times V\) (ordered pairs).
Out-degree \(\mathrm{deg}^+(v)\), in-degree \(\mathrm{deg}^-(v)\).
Loops and bidirected pairs possible depending on model.

Drawings vs abstract graphs

A picture is a representation. The abstract graph is \(V\) and \(E\) only. Two drawings may depict the same graph.

Handshaking lemma

Theorem (undirected). For any finite undirected graph (simple or multi),

\[ \sum_{v\in V}\deg(v) = 2|E|. \]

Proof. Each edge contributes exactly \(2\) to the degree sum (one for each endpoint; a loop contributes 2 to one vertex). Summing degrees counts every edge twice. \(\square\)

Corollary. The number of odd-degree vertices is even.

Proof. \(\sum\deg\) even ⇒ even number of odd summands. \(\square\)

Directed handshaking:

\[ \sum_v \mathrm{deg}^+(v) = \sum_v \mathrm{deg}^-(v) = |E|. \]

Each arc contributes 1 to one out-degree and 1 to one in-degree.

Graphic sequences

A sequence \(d_1\ge d_2\ge\cdots\ge d_n\ge 0\) of integers is graphic if some simple graph on \(n\) vertices has those degrees.

Necessary conditions: \(\sum d_i\) even; each \(d_i\le n-1\).

Havel–Hakimi algorithm

Theorem (Havel–Hakimi). Let \(d_1\ge\cdots\ge d_n\). The sequence is graphic iff the sequence obtained by deleting \(d_1\) and subtracting 1 from the next \(d_1\) terms, then resorting, is graphic (on \(n-1\) vertices). Empty/all-zero is graphic.

Worked use: iterate until zeros (success) or a negative entry / impossibility (fail).

Special graphs

Symbol Name Edges / notes
\(K_n\) Complete \(\binom{n}{2}\) edges; \(\deg=n-1\)
\(P_n\) Path on \(n\) vertices \(n-1\) edges; ends deg 1
\(C_n\) Cycle \(n\ge 3\) \(n\) edges; 2-regular
\(K_{m,n}\) Complete bipartite \(mn\) edges; parts \(m,n\)
\(\overline{G}\) Complement edges of \(K_n\) not in \(G\)
Empty \(E_n\) No edges all deg 0

Regular: all degrees equal \(k\) (\(k\)-regular). \(K_n\) is \((n-1)\)-regular; \(C_n\) is 2-regular.

Isomorphism (awareness)

\(G\cong H\) if there is a bijection \(f:V(G)\to V(H)\) with \(\{u,v\}\in E(G)\iff\{f(u),f(v)\}\in E(H)\).
Same degree sequence is necessary not sufficient. Testing isomorphism is subtle (not needed algorithmically here).

Subgraphs

\(H\) is a subgraph of \(G\) if \(V(H)\subseteq V(G)\) and \(E(H)\subseteq E(G)\).
Induced subgraph: all edges of \(G\) among a vertex subset.

Worked examples

Example 1 — Handshaking

Degrees \(3,3,2,2,2,2\): sum \(14=2|E|\) ⇒ \(|E|=7\). Four odd? Only two odds—OK.

Example 2 — Impossible

Degrees \(3,3,3\): sum 9 odd—impossible.

Example 3 — \(K_5\)

\(|E|=\binom{5}{2}=10\); each deg 4.

Example 4 — \(K_{2,3}\)

Edges \(6\); degrees \(3,3\) on the part of size 2; \(2,2,2\) on the part of size 3.

Example 5 — Havel–Hakimi

Sequence \((3,3,3,1,1,1)\): sort already. Remove 3, subtract from next 3: \((2,2,0,1,1)\) → sort \((2,2,1,1,0)\).
Remove 2: \((1,0,1,0)\) → sort \((1,1,0,0)\).
Remove 1: \((0,0,0)\). Success—graphic.

Example 6 — Havel fail

\((3,3,3,1)\): remove 3 → \((2,2,0)\) sort \((2,2,0)\); remove 2 → \((1,-1)\) negative—not graphic.

Example 7 — Complement degrees

If \(\deg_G(v)=d\), then \(\deg_{\overline{G}}(v)=n-1-d\).

Example 8 — Directed

Arcs \(a\to b, b\to c, a\to c, c\to a\): out-degrees \((2,1,1)\), in \((1,1,2)\); sums = 4.

Example 9 — Max edges simple

On \(n\) verts: \(\binom{n}{2}\). Min for connected: \(n-1\) (trees, Day 61).

Example 10 — Same degree theorem

Any simple \(G\) on \(n\ge 2\) has two vertices of equal degree (Day 45 PHP + no both 0 and \(n-1\)).

Example 11 — \(C_4\) vs \(K_{2,2}\)

\(C_4\cong K_{2,2}\)—same abstract graph.

Example 12 — Multigraph handshaking

Two vertices, three parallel edges: degrees 3,3; sum 6 = \(2\cdot 3\).

Example 13 — Regular existence

Is 3-regular on 5 vertices possible? Sum \(15\) odd—impossible.

Example 14 — \(k\)-regular on \(n\) verts

Need \(kn\) even; \(k\le n-1\). Not always sufficient (e.g. 3-regular on 6 verts exists: utility graph \(K_{3,3}\)).

Example 15 — Count labeled graphs

Number of simple labeled graphs on \(n\) verts: \(2^{\binom{n}{2}}\) (each possible edge in or out).

Exercises

  1. Define simple undirected graph carefully.
  2. Degrees \(4,3,3,2,2,2\): \(|E|\)? Number of odd-degree vertices?
  3. Prove handshaking lemma in your own words.
  4. Prove number of odd-degree vertices is even.
  5. \(|E(K_7)|\) and degree of each vertex.
  6. Draw \(P_5\), \(C_5\), \(K_{1,4}\) (star).
  7. Is \((5,4,3,2,1,1)\) graphic? Run Havel–Hakimi.
  8. Is \((6,5,4,3,2,1,0)\) graphic on 7 verts?
  9. Directed: construct arcs realizing out-degrees \((2,1,0)\) and in-degrees \((1,1,1)\) if possible.
  10. Prove \(\sum\deg^+=\sum\deg^-=|E|\).
  11. Edges in \(k\)-regular graph on \(n\) verts.
  12. Complement of \(C_5\): degrees?
  13. Show \(K_n\) is the unique simple graph with all degrees \(n-1\).
  14. Can a simple graph have degrees \(1,1,1,1\)? Draw or disprove connectivity later—existence: yes \(2K_2\).
  15. Count labeled simple graphs with exactly 1 edge on \(n\) verts.
  16. CS: undirected coauthorship vs directed citation—interpret degree.
  17. Why is \((2,2,2,2)\) graphic two nonisomorphic ways on 4 verts? (\(C_4\) only up to iso for simple connected—actually only \(C_4\). On multigraphs different.)
  18. Havel–Hakimi on \((4,3,3,3,3)\).
  19. Max size of simple bipartite graph on parts \(3+3\).
  20. True/false: same degree sequence ⇒ isomorphic.
  21. Loop contribution to degree: why 2?
  22. Find all nonisomorphic simple graphs on 3 vertices.
  23. If \(\sum\deg=2n-2\) and connected, tree? (preview Day 61: yes.)
  24. Challenge: Erdős–Gállai statement awareness (optional).
  25. Number of simple graphs on 4 labeled verts: \(2^6=64\).

CS connection

  • Social / trust graphs: undirected friendship; directed follow.
  • Dependency graphs: directed packages.
  • Networks: degree distribution as first statistic.
  • Matrix: adjacency matrix \(A\); \(\deg(v)\) = row sum undirected.
  • Resource equality: handshaking as invariant in rewiring.

Common pitfalls

Pitfall What to do instead
Sum of degrees odd accepted Must be even
\(d_i\ge n\) in simple graph Max \(n-1\)
Multigraph vs simple confusion State model
Drawing equality as isomorphism Check abstract \(E\)
Directed degrees mixed Separate in/out

Checkpoint

  • Handshaking proof cold
  • Odd-degree corollary
  • One Havel–Hakimi success and one fail
  • Special graphs table
  • Directed handshaking
  • Exercises 1–15
  • \(2^{\binom{n}{2}}\) labeled count

Two personal takeaways:

  1. …
  2. …

Selected mini-solutions

  1. Sum 16 ⇒ 8 edges; two odds (the two 3s).
  2. \(21\); deg 6.
  3. Try HH… may fail or succeed—work carefully.
  4. Max deg 6 OK; HH: often fails because of 0 with 6 (isolated vs universal)—not graphic.
  5. \(|E|=kn/2\).
  6. \(\binom{\binom{n}{2}}{1}=\binom{n}{2}\).
  7. \((4,3,3,3,3)\) → delete 4 → \((2,2,2,2)\) → \((1,1,2,2)\) sort \((2,2,1,1)\) → \((1,0,1)\) sort \((1,1,0)\) → \((0,0)\) OK.

Deepening notes

Handshaking proof (rewrite)

Each edge \(\{u,v\}\) is counted in \(\deg(u)\) and in \(\deg(v)\). Summing degrees therefore equals \(2|E|\). For loops in multigraphs, the loop is incident twice to its vertex by convention—still +2.

Havel–Hakimi worked checklist

  1. Sort nonincreasing.
  2. If \(d_1>n-1\) or negative appears later → fail.
  3. Delete \(d_1\), subtract 1 from next \(d_1\) entries.
  4. Resort; repeat.
  5. All zeros → graphic.

Degree sequence vs isomorphism

Same degree sequence does not imply isomorphic: e.g. two nonisomorphic graphs on 6 vertices both 2-regular (disjoint cycles \(C_3\cup C_3\) vs \(C_6\)).

Extra drills

D1. Graphic? \((4,4,3,3,2,2)\).
D2. Graphic? \((5,3,3,3,3,3)\).
D3. Edges in 4-regular on 10 verts.
D4. Draw all simple graphs on 4 labeled verts with 2 edges.
D5. Directed handshaking numeric invent.
D6. Complement degrees of \((3,2,2,1)\) on 4 verts.
D7. Prove no 3-regular graph on 5 verts.
D8. \(|E(K_{m,n})|=mn\) proof by product.

Flash

\(\sum\deg=2|E|\); odd degrees even count; labeled graphs \(2^{\binom{n}{2}}\).

Exam drill block

E1. State definitions: simple graph, multigraph, digraph, degree, regular.
E2. Handshaking full proof (undirected + directed).
E3. HH on \((4,3,3,2,2,2)\) step-by-step.
E4. Is \((3,3,3,3,3)\) graphic? Why not?
E5. Edges and degrees in \(K_6\), \(C_6\), \(K_{3,4}\), \(P_6\).
E6. Number of simple labeled graphs on 5 verts; number with exactly 3 edges.
E7. If \(G\) is \(k\)-regular on \(n\) verts, when is \(\overline{G}\) regular and of what degree?
E8. Construct a digraph with out-degrees \((2,2,1,1)\) and equal in-sum.
E9. Prove: in any group of 6 people at a party modeled by a graph, two have same number of handshakes (PHP + degrees).
E10. True/false battery: (i) every sequence of even sum is graphic (ii) \(K_n\) is \((n-1)\)-regular (iii) multigraphs can have odd degree sum.

Mini solutions

E3. Should succeed after few HH steps (verify).
E4. Sum 15 odd—impossible.
E5. \(15\); \(6\); \(12\); \(5\).
E6. \(2^{10}=1024\); \(\binom{10}{3}=120\).
E7. Degree \(n-1-k\) each; always regular.
E10. F; T; F (sum always even).

Special graphs quick sheet

Graph \(|V|\) \(|E|\) Degrees
\(K_n\) \(n\) \(\binom{n}{2}\) \(n-1\) each
\(P_n\) \(n\) \(n-1\) two \(1\)s, rest \(2\)
\(C_n\) \(n\) \(n\) \(2\) each
\(K_{m,n}\) \(m+n\) \(mn\) \(n\) on left, \(m\) on right
\(Q_d\) hypercube \(2^d\) \(d\cdot 2^{d-1}\) \(d\) each

Directed handshaking

\(\sum_v \mathrm{indeg}(v)=\sum_v \mathrm{outdeg}(v)=|A|\) (arc set). Every arc contributes one to one out-degree and one to one in-degree.

Synthesis

Graphs are \(G=(V,E)\) with optional directions and multiplicities. Handshaking \(\sum\deg=2|E|\) forces an even number of odd-degree vertices—the first global invariant. Graphic sequences: Havel–Hakimi or Erdős–Gállai; same degree sequence ≠ isomorphism. Complements, regular graphs, and bipartite complete graphs are the standard zoo.

S1. Full HH on \((5,4,3,3,2,2,1)\)—graphic or not.
S2. Prove no \(3\)-regular graph on \(9\) vertices.
S3. Cold: edges in \(K_7\), \(K_{3,5}\), \(Q_4\); number of odds in any graph.

Modeling hint for later days

Vertices = entities; edges = symmetric relations. Degrees = load/popularity. Tomorrow: moving around the graph (walks, paths, connectivity).

Complement and regularity

If \(G\) is simple on \(n\) vertices with degree sequence \((d_1,\ldots,d_n)\), then \(\overline{G}\) has degrees \((n-1-d_1,\ldots,n-1-d_n)\).
If \(G\) is \(k\)-regular, then \(\overline{G}\) is \((n-1-k)\)-regular.
\(|E(\overline{G})|=\binom{n}{2}-|E(G)|\).

Worked HH recap

Sequence \((3,3,2,2,2)\): sort OK; delete first 3 → subtract from next three → \((2,1,1,2)\) sort \((2,2,1,1)\); delete 2 → \((1,0,1)\) sort \((1,1,0)\); delete 1 → \((0,0)\). Graphic.

More cold drills

C1. Edges in a 4-regular graph on 12 verts.
C2. Why \((2,2,2,2,2)\) is graphic (\(C_5\)) but so is \(C_3\cup C_2\) only if multigraph—simple: \(C_5\) only up to iso on 5 verts 2-regular.
C3. Directed: construct in/out degrees both \((2,1,1,0)\) summing equal.

C1. \(|E|=4\cdot 12/2=24\).

Tomorrow

Day 60 — Paths, cycles, connectivity: walk/trail/path/cycle; components; cut vertices/edges lite; distance; digraph strong connectivity.

Day 60 — Paths, cycles, connectivity

Stage VI · concept day
Goal: Distinguish walk, trail, path, cycle; define connectivity and components; introduce cut vertices/edges lite, distance, diameter; strong connectivity for digraphs.

Why this matters

“Can I get from \(A\) to \(B\)?” is the first algorithmic graph question. Precision about walk vs path prevents sloppy proofs. Connectivity, cuts, and distance underwrite routing, network reliability, and BFS (Day 62).

Theory

Walk, trail, path, cycle

Let \(G\) be undirected.

  • Walk: sequence \(v_0,e_1,v_1,\ldots,e_k,v_k\) with \(e_i=\{v_{i-1},v_i\}\) (often written as vertex sequence if simple graph). Length = number of edges \(k\).
  • Trail: walk with no repeated edge.
  • Path: walk with no repeated vertex (hence no repeated edge).
  • Closed walk: \(v_0=v_k\).
  • Cycle: closed path of length \(\ge 3\) (no repeated vertices except start/end). In simple graphs, cycles are circuits that are paths until return.

Trivial path: single vertex, length 0.

Relations

Every path is a trail; every trail is a walk. Converses false (figure-eight walk can repeat a vertex).

Connectivity (undirected)

\(u\) is connected to \(v\) if some \(u\)–\(v\) path exists.
This is an equivalence relation on \(V\); classes are connected components.
\(G\) is connected if it has exactly one component (any two vertices joined by a path).

Empty edges on \(n\) verts: \(n\) components.

Cut vertices and bridges (lite)

  • Cut vertex (articulation point): vertex whose removal increases the number of components.
  • Bridge (cut edge): edge whose removal increases the number of components.

Trees (Day 61): every edge is a bridge; every non-leaf is a cut vertex (for \(n\ge 3\)).

Distance and diameter

In a connected graph, distance \(d(u,v)\) = length of a shortest \(u\)–\(v\) path.
Eccentricity of \(v\): \(\max_u d(v,u)\).
Diameter \(\mathrm{diam}(G)=\max_{u,v}d(u,v)\).
Radius \(\mathrm{rad}(G)=\min_v\mathrm{ecc}(v)\). Always \(\mathrm{rad}\le\mathrm{diam}\le 2\mathrm{rad}\).

If disconnected, distances between different components are infinite; diameter sometimes defined as infinite or max within components—state convention.

Special distances

  • \(d(v,v)=0\).
  • Triangle inequality: \(d(u,w)\le d(u,v)+d(v,w)\).
  • \(P_n\) has diameter \(n-1\); \(C_n\) has diameter \(\lfloor n/2\rfloor\); \(K_n\) diameter 1 (\(n\ge 2\)).

Directed connectivity

  • Weakly connected: underlying undirected graph connected.
  • Strongly connected: for every ordered pair \((u,v)\), a directed \(u\to\cdots\to v\) path exists.
  • Strong components (SCCs): maximal strongly connected subgraphs; condensation is a DAG (Day 63).

Reachability

Undirected: path existence. Directed: directed path existence (not symmetric).

Edge counts vs connectivity

Connected ⇒ \(|E|\ge |V|-1\).
If \(|E|\ge |V|\), a connected graph has a cycle (Day 61 characterizations).

Walk ⇒ path (formal)

Theorem. If there is a \(u\)–\(v\) walk, then there is a \(u\)–\(v\) path.
Proof. Among all \(u\)–\(v\) walks, choose one of minimal length. If it repeated a vertex \(x\), the closed subwalk between the two visits to \(x\) could be deleted, yielding a shorter \(u\)–\(v\) walk—contradiction. Hence no repeated vertex: it is a path. \(\square\)

Consequently, “connected by a walk” and “connected by a path” define the same relation.

Bridge characterizations

Theorem (lite). For connected \(G\), edge \(e=uv\) is a bridge iff \(e\) lies on no cycle iff \(u\) and \(v\) lie in different components of \(G-e\).
Corollary. If every edge of \(G\) lies on a cycle, \(G\) is \(2\)-edge-connected (bridgeless).

Radius–diameter inequality

Theorem. \(\mathrm{rad}(G)\le \mathrm{diam}(G)\le 2\mathrm{rad}(G)\).
Proof. First inequality: max of distances ≥ min of eccentricities’ dual—formally \(\mathrm{diam}=\max ecc\ge\min ecc=\mathrm{rad}\). Second: take \(u,v\) with \(d(u,v)=\mathrm{diam}\); let \(c\) be a center (\(ecc(c)=\mathrm{rad}\)). Then \(d(u,v)\le d(u,c)+d(c,v)\le 2\mathrm{rad}\). \(\square\)

Worked examples

Example 1 — Classify

In \(C_4\) labeled \(a{-}b{-}c{-}d{-}a\):
\(a,b,c\) is a path; \(a,b,c,d,a\) is a cycle; \(a,b,c,b\) is a walk not a trail (edge \(bc\) wait—if \(a{-}b{-}c{-}b\), edge \(bc\) repeated? \(b{-}c\) then \(c{-}b\) same edge—not a trail).

Example 2 — Components

Two disjoint triangles: 2 components; not connected.

Example 3 — Bridge

Two cliques sharing one vertex: that vertex is a cut vertex; edges inside cliques not bridges.

Example 4 — Path graph

\(P_5\): diameter 4; ends are not cut vertices; internal vertices are cut vertices; every edge is a bridge.

Example 5 — Cycle

\(C_5\): 2-connected (no cut vertex); diameter 2; no bridges.

Example 6 — Distance table

\(K_{1,3}\) (star): center to leaf dist 1; leaf to leaf dist 2; diameter 2.

Example 7 — Directed path

\(a\to b\to c\): strong? No—cannot return. Weak yes if ignore directions.

Example 8 — Tournament lite

Directed complete: strong connectivity not automatic (transitive tournament is not strong).

Example 9 — Shortest path uniqueness

Not unique: \(C_4\) opposite vertices have two shortest paths length 2.

Example 10 — Triangle inequality

In any graph metrics from paths, \(d(u,w)\le d(u,v)+d(v,w)\) by concatenation (may not be a path if vertices repeat—shortcut to path ≤).

Example 11 — Remove bridge

Bridge \(e\): \(G-e\) has exactly one more component if \(G\) connected.

Example 12 — Diameter of hypercube awareness

\(n\)-cube: diameter \(n\) (Hamming distance).

Example 13 — Connected with cycle

\(C_3\) plus pendant edge: connected; has cycle and bridge.

Example 14 — Walk of arbitrary length

If a cycle exists, closed walks of arbitrary large length exist by looping.

Example 15 — SCC example

Vertices \(\{1,2,3\}\) arcs \(1\to 2,2\to 1,2\to 3\): SCCs \(\{1,2\}\) and \(\{3\}\).

Example 16 — Walk not trail

In \(K_3\) with vertices \(a,b,c\): walk \(a{-}b{-}c{-}a{-}b\) repeats edge? Edges \(ab,bc,ca,ab\)—edge \(ab\) repeated: not a trail. Trail example: \(a{-}b{-}c{-}a\) uses each edge once (Eulerian circuit of triangle).

Example 17 — Diameter and radius of \(P_n\)

\(P_n\): ends have ecc \(n-1\); center vertex/vertices have ecc \(\lfloor n/2\rfloor\) or similar. Radius \(\lfloor n/2\rfloor\), diameter \(n-1\). Check \(\mathrm{diam}\le 2\mathrm{rad}\).

Example 18 — Bridge detection

In a tree, every edge is a bridge. In \(C_n\), no bridges. In two cycles sharing an edge, that shared edge may still not be a bridge if alternate paths exist—shared edge of a \(\theta\)-graph is not a bridge.

Example 19 — Distance triangle equality

Equality \(d(u,w)=d(u,v)+d(v,w)\) means \(v\) lies on some shortest \(u\)–\(w\) path.

Example 20 — Directed reachability asymmetry

\(a\to b\to c\): \(a\) reaches \(c\), \(c\) does not reach \(a\). Undirected collapse would connect all three.

Exercises

  1. Define walk, trail, path, cycle in one line each.
  2. Give an example of a trail that is not a path.
  3. Prove: if a walk from \(u\) to \(v\) exists, a path from \(u\) to \(v\) exists (delete cycles).
  4. Components of \(P_3\cup K_2\).
  5. Diameter of \(C_6\), \(P_6\), \(K_6\).
  6. Find all cut vertices of a path \(P_n\).
  7. Find all bridges of a tree preview: all edges.
  8. Star \(K_{1,n}\): cut vertices? Bridges? Diameter?
  9. Digraph: draw a weakly but not strongly connected example.
  10. Prove connectivity is an equivalence relation (undirected).
  11. True/false: removing a non-bridge edge keeps connectivity of a connected graph.
  12. Graph with diameter 1: characterize (\(K_n\)).
  13. Can diameter be 2 with a bridge? Example or no.
  14. Distance from \(u\) to \(v\) in a connected graph is at most \(n-1\). Why?
  15. \(K_{2,3}\): diameter? Bipartite cycles?
  16. CS: web pages as digraph—strong connectivity meaning.
  17. Eccentricity of center of a star vs leaf.
  18. Prove \(\mathrm{diam}\le 2\mathrm{rad}\) sketch.
  19. Number of paths between two vertices in \(K_n\) of length 2.
  20. If every vertex degree ≥2 in simple \(G\), show a cycle exists (standard).
  21. Directed: in/out connectivity differences for reachability.
  22. Build a graph with 6 verts, diameter 3, one bridge.
  23. Challenge: block-cut tree awareness (optional).
  24. List distances in \(C_5\) from one vertex.
  25. Prove: \(G\) connected with \(|E|=|V|-1\) has no cycle (tree half—Day 61).

CS connection

  • Routing / reachability in networks.
  • Garbage collection / mark phase: reachability from roots.
  • Build systems: dependency reachability.
  • Social graphs: distance = degrees of separation.
  • Fault tolerance: bridges and cut vertices as single points of failure.

Common pitfalls

Pitfall What to do instead
Calling any walk a path No repeated vertices for path
Cycle length 2 in simple graphs Need ≥3
Distance in disconnected graphs Undefined or ∞
Directed path vs undirected Arcs orientation matters
Cut vertex vs isolated removal drawing error Recompute components of \(G-v\)

Checkpoint

  • Walk/trail/path/cycle hierarchy
  • Components as equivalence classes
  • Distance and diameter definitions
  • Cut vertex / bridge lite
  • Strong vs weak connectivity
  • Exercises 1–15
  • Proof: walk ⇒ path exists

Two personal takeaways:

  1. …
  2. …

Selected mini-solutions

  1. In a graph with a vertex of degree 3, a trail can revisit the vertex using different edges.
  2. Among \(u\)–\(v\) walks, take one of minimal length—must be a path (else cycle shortcut).
  3. \(3\), \(5\), \(1\).
  4. Center is only cut vertex for \(n\ge 2\); all edges bridges; diameter 2.
  5. True if the edge is not a bridge.
  6. Shortest path has ≤ \(n-1\) edges (no vertex repeat).
  7. Longest path ends have neighbors on the path → cycle.

Deepening notes

Walk-to-path algorithm

Given a \(u\)–\(v\) walk, while a repeated vertex \(x\) appears, delete the closed subwalk between the two visits to \(x\). Length decreases; eventually a path remains. Hence connectivity can be defined via walks or paths equivalently.

Distance axioms (path metric)

On a connected graph, \(d\) is a metric: identity of indiscernibles for vertices, symmetry, triangle inequality. Discrete geodesic metric.

Cut edge test

Edge \(e=uv\) is a bridge iff \(e\) lies on no cycle iff \(d_{G-e}(u,v)=\infty\).

Extra drills

D1. Classify sequences in \(K_4\) as walk/trail/path.
D2. Components of three disjoint edges on 7 verts (one isolated).
D3. Diameter of hypercube \(Q_3\).
D4. Cut vertices of two cliques sharing a vertex.
D5. Strong connectivity of a directed cycle.
D6. Prove \(d\le n-1\) on connected \(n\)-vertex graphs.
D7. BFS layers as distances (preview Day 62).
D8. Find bridges in a figure-8 graph (two cycles share vertex—none).

Flash

path ⇒ trail ⇒ walk; connected ⇔ one component; \(\mathrm{diam}=\max d(u,v)\); strong = directed paths both ways.

Exam drill block

E1. Give examples distinguishing walk, trail, path, cycle in \(K_4\).
E2. Prove: existence of \(u\)–\(v\) walk ⇒ existence of \(u\)–\(v\) path.
E3. Components and diameter of \(C_3\cup P_4\).
E4. All bridges and cut vertices of \(P_6\).
E5. Distance matrix for \(C_5\) from one vertex.
E6. Digraph: make weakly but not strongly connected on 4 verts.
E7. Prove connectivity relation is equivalence (undirected).
E8. If \(G\) connected and \(|E|\ge|V|\), show a cycle exists (hint: spanning tree).
E9. Star \(K_{1,n}\): list ecc of center and leaves; radius; diameter.
E10. True/false: (i) every trail is a path (ii) diameter of \(K_n\) is 1 for \(n\ge 2\) (iii) bridges lie on no cycle.

Mini solutions

E3. 2 components; diam max of 1 and 3 = 3 within comps—state convention for disconnected.
E4. All edges bridges; cut verts = internal.
E5. Distances \(0,1,2,2,1\).
E9. Center ecc 1; leaf ecc 2; rad 1; diam 2.
E10. F; T; T.

Deep dive — Connectivity as reliability

Cut vertices and bridges are single points of failure. In network design, requiring \(2\)-connectivity (no cut vertex) or \(2\)-edge-connectivity (no bridge) is a reliability spec. Redundant paths mean \(d_{G-e}(u,v)<\infty\) for every edge \(e\) on a path. Distance and diameter bound latency in hops; BFS (Day 62) computes all distances from a source in \(O(n+m)\).

Synthesis

Walk ⊇ trail ⊇ path; cycles close paths. Connectivity partitions \(V\) into components via an equivalence relation. Distance is shortest-path length; diameter/radius summarize shape. Directed graphs split weak vs strong connectivity. Bridges lie on no cycle—trees are all bridges.

S1. Prove carefully: connectivity is an equivalence relation on \(V\).
S2. List all bridges and cut vertices of two triangles joined by a single edge.
S3. Compute radius and diameter of \(C_7\) and of \(K_{1,6}\).
S4. Give a digraph on 4 vertices that is weakly connected, not strongly; identify SCCs.
S5. Prove: if \(G\) is simple connected with \(n\) vertices and \(n\) edges, then \(G\) has exactly one cycle (structure lite).

Flash-plus distance table

Graph Radius Diameter Notes
\(K_n\) (\(n\ge 2\)) 1 1
\(P_n\) \(\lceil(n-1)/2\rceil\) \(n-1\) center middle
\(C_n\) \(\lfloor n/2\rfloor\) \(\lfloor n/2\rfloor\)
\(K_{1,n}\) 1 2 star
\(Q_d\) \(d\) \(d\) hypercube

Tomorrow

Day 61 — Trees: equivalent characterizations; rooted/binary trees; Catalan link; spanning trees; Cayley’s formula; Kruskal/Prim cut property idea.

Day 61 — Trees

Stage VI · concept day
Goal: Master equivalent characterizations of trees with a proof cycle; rooted and binary trees; Catalan link; spanning trees; Cayley’s formula \(n^{n-2}\); Kruskal/Prim correctness idea via the cut property (no coding).

Why this matters

Trees are the minimally connected graphs—unique paths, hierarchical data, spanning backbones of networks, and the structure of recursive computation. Spanning trees and MST algorithms (Kruskal, Prim) are core CS; Cayley counts labeled trees. Binary tree shapes reconnect to Catalan numbers (Day 50).

Theory

Definition and characterizations

A tree is an undirected graph that is connected and acyclic.

Theorem (equivalent conditions). For a simple graph \(G\) with \(n\ge 1\) vertices, TFAE:

  1. \(G\) is a tree (connected + acyclic).
  2. \(G\) is connected and \(|E|=n-1\).
  3. \(G\) is acyclic and \(|E|=n-1\).
  4. Any two vertices are joined by a unique path.
  5. \(G\) is connected, but removing any edge disconnects \(G\) (every edge is a bridge).
  6. \(G\) is acyclic, but adding any missing edge creates exactly one cycle.

Proof cycle (sketch).

  • \((1)\Rightarrow(4)\): connected ⇒ path exists; two distinct paths would form a cycle—contradiction to acyclic.
  • \((4)\Rightarrow(1)\): unique path ⇒ connected; a cycle would give two paths between some pair.
  • \((1)\Rightarrow(2)\): induction on \(n\). \(n=1\): OK. Tree \(n\ge 2\) has a leaf (deg 1)—remove leaf, \(|E|\) drops by 1, IH on \(n-1\).
  • \((2)\Rightarrow(1)\): connected with \(|E|=n-1\) cannot have a cycle (cycle ⇒ can remove edge stay connected ⇒ would have connected spanning with fewer than \(n-1\) edges—contradiction to min \(n-1\)). More carefully: any connected graph has a spanning tree with \(n-1\) edges; if already \(|E|=n-1\) and connected, that spanning tree is \(G\) itself ⇒ acyclic.
  • \((3)\Rightarrow(1)\): acyclic with \(n-1\) edges: number of components in a forest is \(n-|E|=1\) ⇒ connected.
  • \((1)\Leftrightarrow(5),(6)\): standard using unique paths / bridges.

Forest: acyclic graph (components are trees). For a forest with \(n\) verts and \(c\) components: \(|E|=n-c\).

Leaves

Tree \(n\ge 2\) has at least two leaves (deg 1 vertices)—from handshaking: \(\sum\deg=2n-2\), if ≤1 leaf then sum ≥ \(2+2(n-1)\) or similar contradiction.

Rooted trees

Choose a root \(r\); orient edges away from (or toward) the root.
Parent / child / ancestor / descendant / depth / height standard.
Rooted structure is extra data beyond the undirected tree.

Binary trees and Catalan

Plane binary trees with \(n\) internal nodes (or full binary trees with \(n+1\) leaves, conventions vary): counted by Catalan \(C_n\).
Recursive structure: root + left subtree + right subtree gives Catalan convolution recurrence.

Binary search tree shapes on \(n\) keys: \(C_n\) plane binary trees (keys determine embedding once shape + inorder fixed).

Spanning trees

A spanning tree of connected \(G\) is a subgraph that is a tree on all vertices of \(G\) (connects all, \(|E|=n-1\), acyclic).

Existence: \(G\) connected ⇔ \(G\) has a spanning tree (grow acyclic connected subgraph maximally / delete edges on cycles).

Number of spanning trees \(\tau(G)\): Kirchhoff matrix-tree theorem (awareness); special cases below.

Cayley’s formula

Theorem (Cayley). Number of distinct trees on \(n\) labeled vertices is

\[ n^{n-2}. \]

Equivalently: number of spanning trees of \(K_n\) is \(n^{n-2}\).

Examples: \(n=2\): \(1\); \(n=3\): \(3\); \(n=4\): \(16\).
Prüfer code bijects labeled trees with sequences in \([n]^{n-2}\) (awareness).

Minimum spanning tree (MST) idea

Given connected weighted undirected \(G\) with edge weights, an MST is a spanning tree of minimum total weight.

Cut property (idea). For any partition of \(V\) into \(S\) and \(V\setminus S\), a lightest edge crossing the cut is safe to include in some MST (assuming distinct weights for simplicity).

Kruskal idea: sort edges by weight ascending; add next edge if it does not create a cycle (union-find culture). Correct by cut/cycle properties.

Prim idea: grow a tree from a start vertex; always add lightest edge from tree vertices to outside. Correct by cut property.

No coding today—hand-simulate on tiny graphs.

Cycle property (lite)

Heaviest edge on any cycle is not in any MST (distinct weights).

Worked examples

Example 1 — Check tree

Graph: \(n=5\), edges 4, connected, no cycle → tree.

Example 2 — Not tree

\(n=5\), edges 5, connected → has a cycle.

Example 3 — Forest

\(n=10\), \(c=3\) tree components: \(|E|=7\).

Example 4 — Unique path

In a tree, path between two vertices is unique—use to define ancestry in rooted tree.

Example 5 — Cayley

Labeled trees on 4 verts: \(4^{2}=16\).

Example 6 — Spanning trees of \(C_n\)

Any spanning tree of \(C_n\) omits exactly one edge: \(n\) spanning trees.

Example 7 — Spanning trees of \(K_4\)

\(4^{2}=16\) (Cayley).

Example 8 — Kruskal hand

Vertices \(A,B,C,D\). Weights: \(AB1,AC3,BC2,BD4,CD5\).
Order: AB, BC, AC (skip cycle), BD, CD skip. Tree: AB,BC,BD weight \(1+2+4=7\).

Example 9 — Prim hand

Start \(A\): take AB (1); from \(\{A,B\}\) take BC (2); from \(\{A,B,C\}\) take BD (4). Same tree.

Example 10 — Catalan binary trees

\(n=3\) internal: \(C_3=5\) shapes.

Example 11 — Leaf count

Path \(P_n\): 2 leaves. Star: \(n-1\) leaves.

Example 12 — Add edge

Tree + any new edge: unique cycle (along previous unique path + new edge).

Example 13 — Remove edge

Tree − any edge: exactly 2 components.

Example 14 — Rooted depths

Root a path at an end: height \(n-1\); root at center: smaller height.

Example 15 — Cut property

Partition \(\{A\}\) vs rest; lightest edge from \(A\) is in some MST—Prim’s first step.

Exercises

  1. State 4 equivalent characterizations of a tree.
  2. Prove: connected + \(|E|=n-1\) ⇒ acyclic (sketch).
  3. Prove: tree ⇒ unique paths.
  4. Forest: \(n=12\), \(|E|=9\) ⇒ how many components?
  5. Prove tree \(n\ge 2\) has ≥2 leaves.
  6. Cayley: number for \(n=5,6\).
  7. Spanning trees of \(C_6\).
  8. Kruskal on a 5-vertex weighted graph you draw (list edges).
  9. Prim on the same graph from two different starts—same weight?
  10. Why Kruskal rejects an edge: cycle check meaning.
  11. Binary trees: \(C_4=14\) shapes with 4 internal nodes.
  12. True/false: every tree is bipartite. (True—no odd cycle.)
  13. Center of a tree lite: one vertex or two adjacent.
  14. Count labeled stars on \(n\) verts: \(n\) (choose center).
  15. CS: DOM tree / filesystem tree—rooted.
  16. Prove \(|E|=n-c\) for forests.
  17. \(K_{2,3}\) spanning trees count (optional enumeration).
  18. If \(G\) has a cycle, spanning trees omit at least one cycle edge.
  19. MST unique if all weights distinct—true.
  20. Counterexample idea: equal weights, multiple MSTs.
  21. Prüfer: decode a small sequence (optional).
  22. Height vs number of nodes binary tree bounds.
  23. Challenge: Kirchhoff theorem statement for \(K_n\) recovers Cayley.
  24. Connected unicyclic (\(|E|=n\)) : not a tree; removing any cycle edge yields a tree.
  25. Portfolio: prove \((1)\Leftrightarrow(4)\Leftrightarrow(2)\) carefully in writing.

CS connection

  • File systems, DOM, ASTs, call trees.
  • Union-find / Kruskal for clustering and networks.
  • Routing trees / Steiner culture.
  • Decision trees in ML (rooted, not free trees).
  • Spanning tree protocol in networks (name drop).

Common pitfalls

Pitfall What to do instead
Connected ⇔ tree Need acyclic too
\(|E|=n-1\) alone Need connected or acyclic
Cayley for unlabeled trees Cayley is labeled
MST algorithms as black boxes Cut property intuition
Confusing rooted binary with free trees Root + plane embedding

Checkpoint

  • TFAE list for trees
  • Proof sketches unique path + edge count
  • Forest formula \(|E|=n-c\)
  • Cayley \(n^{n-2}\) with small checks
  • Kruskal/Prim hand sim + cut property sentence
  • Catalan–binary tree link
  • Exercises 1–15

Two personal takeaways:

  1. …
  2. …

Selected mini-solutions

  1. \(c=n-|E|=3\).
  2. \(5^3=125\); \(6^4=1296\).
  4. True.
  5. \(n\).
  6. Each component tree: sum \((n_i-1)=n-c\).
  7. Distinct weights ⇒ unique lightest choices—MST unique.

Deepening notes

Proof that trees have ≥2 leaves (\(n\ge 2\))

\(\sum\deg=2n-2\). If ≤1 leaf, then at most one deg-1 and others ≥2: sum ≥ \(1+2(n-1)=2n-1>2n-2\), contradiction. (If zero leaves all ≥2: sum ≥\(2n>2n-2\).)

Cayley small values

\(n\) \(n^{n-2}\)
1 1 (convention)
2 1
3 3
4 16
5 125

Kruskal vs Prim comparison

Kruskal Prim
Grows forest → tree single tree
Edge order global sorted lightest cut edge
Cycle check yes (union-find) automatic if only cut edges
Cut property both rely on it

Extra drills

D1. Prove unique path ⇒ acyclic.
D2. Forest edges for \(n=20\), \(c=5\).
D3. Cayley \(n=6\).
D4. Spanning trees of \(K_5\).
D5. Kruskal on 6 edges weights 1..6 of a graph you draw.
D6. Binary trees \(C_5=42\).
D7. Root path at center vs end—heights.
D8. Add edge to tree: describe the unique cycle.

Flash

Tree ⇔ connected acyclic ⇔ \(|E|=n-1\) connected; Cayley \(n^{n-2}\); MST cut property.

Exam drill block

E1. List 4 TFAE for trees; prove unique path ⇒ acyclic.
E2. Forest formula: \(n=30\), \(c=7\) edges?
E3. Cayley values \(n=2..6\).
E4. Spanning trees of \(C_8\) and of \(K_4\).
E5. Kruskal on weights you invent (5 verts, 7 edges)—trace.
E6. Prim from two starts—same total weight?
E7. Why every edge of a tree is a bridge.
E8. Binary plane trees: \(C_2,C_3,C_4\).
E9. Tree + new edge: prove exactly one cycle.
E10. True/false: (i) Cayley counts unlabeled trees (ii) MST unique if weights distinct (iii) every tree is bipartite.

Mini solutions

E2. \(23\).
E3. \(1,3,16,125,1296\).
E4. \(8\); \(16\).
E8. \(2,5,14\).
E10. F; T; T.

TFAE for trees (keep all four)

For a simple graph \(G\) on \(n\ge 1\) vertices, TFAE:

  1. \(G\) is connected and acyclic.
  2. \(G\) is connected and \(|E|=n-1\).
  3. \(G\) is acyclic and \(|E|=n-1\).
  4. Unique path between every pair of vertices.

Leaf count: \(n\ge 2\) ⇒ at least two leaves (deg-1 vertices).

Spanning tree facts

  • Connected \(G\) has a spanning tree; any spanning tree has \(n-1\) edges.
  • Adding any non-tree edge to a spanning tree creates exactly one cycle.
  • Number of distinct spanning trees of \(K_n\): Cayley \(n^{n-2}\) (labeled).
  • \(C_n\) has exactly \(n\) spanning trees (delete any one edge).

Cut property (idea for MST)

For a cut \((S,V\setminus S)\), a lightest edge across the cut is safe to include in some MST. Kruskal and Prim both rest on this; correctness proofs differ in bookkeeping (union-find vs growing a single tree).

Synthesis

Trees are the minimal connected graphs and the maximal acyclic ones. Characterizations interchange connectivity, acyclicity, edge count, and unique paths. Cayley counts labeled spanning trees of \(K_n\). MST algorithms (Kruskal/Prim) select light safe edges via the cut property. Plane binary trees reconnect to Catalan numbers.

S1. Prove unique path ⇒ acyclic and connected ⇒ tree.
S2. Kruskal trace on a 6-vertex weighted graph of your choice.
S3. Cold: Cayley \(n=5\); spanning trees of \(C_6\); leaves in any tree \(n\ge 2\).

S4. Prove every tree with \(n\ge 2\) has at least two leaves (handshaking).
S5. Why MST is unique when all edge weights are distinct (sketch).

Tomorrow

Day 62 — BFS & DFS: levels; shortest unweighted; discovery/finish; edge types awareness; hand simulation tables.