Day 60 — Paths, cycles, 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

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