Skip to main content

Degrees, Walks, Paths, Cycles, and Connectivity

What This Concept Is​

These are the core structural notions of graph theory, each capturing a different scale at which a graph can be analyzed:

  • degree $\deg(v)$: number of edges incident to a vertex $v$ (self-loops counted twice by convention). For directed graphs, there is in-degree and out-degree.
  • walk: a sequence $v_0, e_1, v_1, e_2, \ldots, v_k$ where each $e_i$ is an edge connecting $v_{i-1}$ and $v_i$. Vertices and edges may repeat.
  • trail: a walk with no repeated edge.
  • path: a walk with no repeated vertex (and therefore no repeated edge either).
  • cycle: a closed path -- starts and ends at the same vertex, no other repeats; length $\ge 3$ in simple graphs.
  • connected graph: an undirected graph where every pair of vertices can be joined by a walk (equivalently, by a path).
  • connected component: a maximal connected subgraph.
  • strongly / weakly connected (directed): every pair reachable in both directions / reachable in the underlying undirected graph.

The hierarchy is important: every path is a trail is a walk, but not conversely. Many theorems require the stricter form, so the vocabulary must be exact.

These notions describe how local edge information scales into global structure. Degree is the most local; connectivity is the most global. Paths and cycles mediate between the two.

Distance. The distance $d(u, v)$ between two vertices of a connected graph is the length of the shortest path from $u$ to $v$ (and $\infty$ if no such path exists). The diameter of a graph is $\max_{u, v} d(u, v)$; the girth is the length of its shortest cycle. Diameter and girth are the two extremal measures of "how stretched out" and "how tight" a graph is, and they will reappear in routing (Semester 5) and network-fault tolerance (Semester 6).

Why It Matters Here​

Degree arguments produce fast structural proofs. Path and connectivity language turn vague ideas like "the network hangs together" into precise claims with known algorithms for verification. Tree theorems (cluster 5), Euler questions (cluster 6), planarity proofs (cluster 6) all depend on these notions as basic building blocks.

Downstream: BFS/DFS (Semester 2) compute connectivity and shortest paths; cycle detection is the basis for deadlock detection (Semester 5 OS) and dependency validation (Semester 3 build systems); strongly connected components power dataflow analyses and distributed consensus impossibility proofs (Semester 6).

Cuts and bridges. A bridge is an edge whose removal disconnects the graph; a cut vertex is a vertex whose removal disconnects the graph. Together they form the vocabulary of fragility: the more bridges a network has, the more fragile its connectivity. Network-reliability questions in Semester 6 ("how many simultaneous link failures does our service survive?") are cut arguments in disguise.

Concrete Examples​

Example 1: handshaking lemma. For any undirected graph $G = (V, E)$:

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

Why? Every edge contributes exactly $2$ to the degree sum -- one for each endpoint. Sum over edges; every vertex-edge incidence is counted once per edge end.

Consequences:

  • The number of odd-degree vertices is always even. (Proof: the sum of degrees is even, and the sum of even degrees is even, so the sum of odd degrees must be even; a sum of an odd number of odd numbers is odd, contradiction.)
  • In a $k$-regular graph (all vertices have degree $k$), $|E| = k|V|/2$; in particular, $k|V|$ must be even -- so no $3$-regular graph exists on an odd number of vertices.
  • Complete graph $K_n$ has every vertex of degree $n-1$, so $|E(K_n)| = n(n-1)/2$, matching $\binom{n}{2}$.

Example 2: walk-count identity via matrix powers. Define the adjacency matrix $A$ by $A_{ij} = 1$ if $ij \in E$, else $0$. Then $(A^k)_{ij}$ equals the number of walks of length exactly $k$ from $i$ to $j$.

Proof sketch: For $k = 1$, direct by definition. For $k = 2$: $(A^2){ij} = \sum_m A{im} A_{mj}$, which sums over intermediate vertices $m$, contributing $1$ each time $im \in E$ and $mj \in E$ -- exactly a length-$2$ walk count. Induction gives the general case.

This is the matrix incarnation of the product rule for counting walks by their middle vertices.

Corollary: if $(A^k){ij} > 0$ for some $k$, then there is a walk from $i$ to $j$, hence a path. Hence $(I + A + A^2 + \cdots + A^{n-1}){ij} > 0$ iff $i$ and $j$ are in the same component -- a purely linear-algebraic connectivity test.

Example 3: path-connectedness is transitive. In an undirected graph, if $u$-to-$v$ and $v$-to-$w$ paths exist, so does a $u$-to-$w$ walk (concatenate). The walk can be reduced to a path by removing detours at repeated vertices. So reachability is transitive; combined with reflexivity and symmetry (undirected), it is an equivalence relation -- whose equivalence classes are exactly the connected components.

Common Confusion / Misconceptions​

  • Walk vs path. A walk allows revisits; a path does not. Many theorems (e.g., uniqueness of paths in a tree) are false for walks. Read theorems carefully.
  • Connected vs complete. Connected means every pair can be joined somehow; complete means every pair is joined directly by an edge. $K_5$ is complete; a tree on $5$ vertices is connected but far from complete.
  • Cycle length conventions. In simple graphs, cycles have length $\ge 3$; a length-$2$ "cycle" would be a pair of parallel edges (allowed only in multigraphs). A self-loop is sometimes considered a length-$1$ cycle but is usually excluded in simple-graph discussions.
  • Directed vs undirected reachability. In directed graphs, "connected" splits into strongly (paths in both directions) and weakly (connected in the underlying undirected graph). They are very different properties.
  • "High average degree means connected." Not necessarily: a graph made of two large cliques is far from connected yet has high average degree. Average or minimum degree is evidence about local structure; connectivity is a global reachability statement, and no direct implication flows from the former to the latter without further assumptions.

How To Use It​

Use degree arguments when you need:

  • parity (odd/even counts)
  • average local density ($\bar d = 2|E|/|V|$)
  • fast contradictions via handshaking
  • bounds on regular or near-regular structure

Use paths and connectivity language when you need:

  • reachability / escape-from-region questions
  • component structure
  • minimal or maximal connection arguments (bridges, cut vertices)
  • proofs by walking along a chosen path

Walk-to-path reduction. If you can show a walk from $u$ to $v$, you can always extract a path: scan left to right and, whenever a vertex repeats, delete the segment between its two occurrences. The resulting sequence has no repeated vertex and still connects $u$ to $v$.

Operational workflow:

  1. classify the claim: is it local (degree), mid-scale (paths/cycles), or global (connectivity)?
  2. for degree claims, sum $\deg(v)$ and use handshaking for parity.
  3. for path claims, consider BFS/DFS order: each layer gives a distance bound.
  4. for cycle claims, use the pigeonhole on visited vertices along a walk.
  5. for connectivity, appeal to equivalence-class structure or component counts.
  6. for adjacency-matrix claims, remember $(A^k){ij}$ counts walks and $(A+I)^k{ij}$ captures walks of length $\le k$.
  7. always verify on the smallest graph that exhibits the property ($K_3, K_4, C_4, P_3$).
  8. when in doubt, run a BFS in your head from one vertex and inspect the distance-layer structure -- the BFS tree exposes connectivity, shortest paths, and the absence of odd cycles (for bipartiteness checks) all at once.

Transfer / Where This Shows Up Later​

  • Semester 2 algorithms: BFS computes shortest paths in unweighted graphs; DFS detects cycles and computes topological order. Strongly connected components (Kosaraju, Tarjan) are built from DFS traversal. All use the path/walk distinction.
  • Semester 3 data structures: adjacency list vs matrix choice governs time/space trade-offs. Union-find maintains connected components in near-constant amortized time.
  • Semester 4 databases: query optimizer plans are graphs; "join order" selection is a reachability computation over the schema graph.
  • Semester 5 OS: deadlock detection finds cycles in resource-wait graphs; process dependency analysis is reachability in the DAG of process relationships.
  • Semester 6 distributed systems: consensus in asynchronous networks depends on the communication graph's connectivity; quorum systems use intersection properties that are degree/counting arguments.
  • Semester 7 architecture: call graphs of microservices; detecting illegal cross-module dependencies is cycle/reachability checking in the module dependency graph (a fitness-function application).

Check Yourself​

  1. Why must the number of odd-degree vertices be even? Write the proof as three crisp sentences.
  2. What is the difference between a walk, a trail, and a path?
  3. Can a connected graph contain cycles? Can a disconnected graph?
  4. Write out $A^2$ for the path $P_3$ (three vertices in a line) and verify the walk-count interpretation.
  5. Prove: every graph with minimum degree $\ge 2$ contains a cycle. (Hint: follow edges; use pigeonhole.)
  6. Why does the handshaking lemma extend to multigraphs (with self-loops counting twice) without modification?

Mini Drill or Application​

For each statement, say whether degree counting, path language, or cycle reasoning is the best first tool, then justify:

  1. A graph has all vertices of degree $2$. (What does it look like?)
  2. A graph splits into three disconnected components. (What local signal reveals each?)
  3. A graph has exactly two odd-degree vertices. (What traversal does handshaking allow?)
  4. A graph is $3$-regular on $7$ vertices. (Is this possible?)
  5. Given a graph $G$, compute $|E|$ from $\sum \deg(v)$.
  6. Classify a graph of all vertices of degree exactly $k$ into the category "$k$-regular" and propose three examples.
  7. In a connected graph on $n$ vertices, what is the minimum number of edges? (Tree = $n - 1$.) What is the maximum? ($K_n$ = $n(n-1)/2$.)
  8. Show that if every vertex of a simple graph on $n$ vertices has degree $\ge n/2$, then the graph is connected. (Hint: any two vertices' neighborhoods must intersect.)
  9. Given the adjacency matrix $A$, explain why the diagonal entries of $A^3$ count closed walks of length $3$, and why those are three times the number of triangles in the graph.

Read This Only If Stuck​