Degrees, Paths, Cycles, and Connectivity - Discrete Math

SECTION 1

Historical Context & Motivation

Graph theory traces its origins to a deceptively simple puzzle about bridges. In 1736, the Swiss mathematician Leonhard Euler asked whether one could walk through the city of Königsberg, crossing each of its seven bridges exactly once. By abstracting the landmasses as vertices and the bridges as edges, Euler proved that no such walk existed — and in doing so, he created the first theorem of graph theory. His argument hinged on the notion of vertex degree: unless exactly zero or two vertices have an odd number of incident edges, a traversal visiting every edge once is impossible. This single insight revealed that local structural counts could determine global traversal properties.

Over the next two centuries, the concepts of paths, cycles, and connectivity evolved from ad hoc observations into a rigorous framework. The rise of electrical engineering, operations research, and computer science in the twentieth century transformed graph theory from a mathematical curiosity into an indispensable tool for modeling networks of all kinds — from circuit boards to social networks to the internet itself.

1736 • Euler and the Königsberg Bridges

Euler formalized the Königsberg bridge problem, introducing the notion of vertex degree and proving that an Eulerian path requires at most two vertices of odd degree.

1847 • Kirchhoff's Circuit Laws

Gustav Kirchhoff used graph-theoretic trees and cycles to analyze electrical circuits, establishing the matrix-tree theorem and linking connectivity to linear algebra.

1936 • König's Textbook

Dénes König published the first comprehensive textbook on graph theory, systematizing definitions of paths, cycles, and connected components.

1956 • Dijkstra's Shortest Path Algorithm

Edsger Dijkstra developed his shortest-path algorithm, demonstrating that path-finding in graphs is not only theoretically rich but computationally tractable.

1970s • Network Reliability & k-Connectivity

Researchers formalized vertex- and edge-connectivity measures to quantify network robustness, motivating Whitney's and Menger's theorems in applied settings.

The central question this lesson addresses is: given a graph, what can we infer about its structure from vertex degrees, and how do we formalize the ideas of traversal (paths and cycles) and wholeness (connectivity)? These concepts form the bedrock upon which nearly every other graph-theoretic result is built.

SECTION 2

Core Principles & Definitions

Before diving into theorems and algorithms, we need a precise shared vocabulary. A graph G = (V, E) consists of a finite set V of vertices and a set E of edges, where each edge is an unordered pair of vertices (in an undirected graph) or an ordered pair (in a directed graph). The four pillars of this lesson — degrees, paths, cycles, and connectivity — describe local, sequential, and global properties of this structure.

Degree of a Vertex

The degree deg(v) of a vertex v is the number of edges incident to v. In a directed graph, we distinguish in-degree (edges arriving at v) from out-degree (edges leaving v). A vertex with degree 0 is called isolated.

Path

A path is a sequence of distinct vertices v₁, v₂, …, vₖ such that each consecutive pair is joined by an edge. The length of the path is k − 1, counting edges. A path that visits every vertex of G exactly once is called a Hamiltonian path.

Cycle

A cycle is a path whose first and last vertices coincide, with all other vertices distinct and at least three edges present. A graph with no cycles is called acyclic; a connected acyclic graph is a tree.

Connectivity

A graph is connected if there exists a path between every pair of vertices. More refined measures include vertex connectivity κ(G) and edge connectivity λ(G), which count the minimum number of vertices or edges whose removal disconnects G.

The Handshaking Lemma

The sum of all vertex degrees in any undirected graph equals exactly twice the number of edges: Σ deg(v) = 2|E|. This seemingly obvious identity is the first non-trivial theorem students encounter and underpins many counting arguments.

✦

KEY TAKEAWAY

Think of a graph as a road network. The degree of an intersection is the number of roads meeting there. A path is a route that never revisits an intersection. A cycle is a loop that brings you back to your starting point. Connectivity tells you whether you can drive from any intersection to any other — and how many roads or intersections could be closed before the network falls apart. These four ideas capture the local count (degree), the sequential traversal (path and cycle), and the global resilience (connectivity) of any network.

SECTION 3

Visual Explanation — Anatomy of a Graph

The diagram below illustrates a single undirected graph with seven vertices and nine edges. It has been annotated to highlight key structural features: vertex degrees are shown next to each vertex, a path from vertex A to vertex F is traced in cyan, a cycle through vertices B–C–D–E–B is shown in pink, and the graph's single connected component is evident from the fact that every vertex can be reached from every other.

Graph G has 7 vertices and 9 edges. The cyan dashed line traces a path of length 4 from A to F. The pink solid line marks a 4-cycle through B, C, D, and E. Degree labels appear next to each vertex. Note that the sum of degrees is 3 + 3 + 4 + 3 + 3 + 1 + 1 = 18 = 2 × 9, confirming the Handshaking Lemma.

Several observations emerge from the diagram. First, vertex C has the highest degree (4), meaning it is the most "connected" node locally. Second, the path A–B–D–E–F visits five of the seven vertices without repetition, illustrating that a path need not span the entire graph. Third, the cycle B–C–D–E–B (equivalently B–C–E–D–B depending on which edges exist) forms a closed loop of length 4. Finally, vertex G is a pendant vertex (degree 1), connected to the rest of the graph by a single edge — removing that edge would isolate G and make the graph disconnected.

SECTION 4

Mathematical Framework

The formal machinery underlying degrees, paths, cycles, and connectivity is remarkably elegant. We present the key results as named equations and theorems, together with the notation needed to state them precisely.

HANDSHAKING LEMMA

Σ_{v ∈ V} deg(v) = 2 |E|

Every edge contributes exactly 1 to the degree of each of its two endpoints, so the sum over all vertex degrees counts each edge twice. A corollary: the number of vertices with odd degree is always even.

DEGREE SEQUENCE CONSTRAINT

0 ≤ deg(v) ≤ n − 1 for all v ∈ V, where n = |V|

In a simple graph (no loops or multi-edges), each vertex can be adjacent to at most n − 1 others. A sequence of non-negative integers is graphical (realizable as a simple graph's degree sequence) if and only if it satisfies the Erdős–Gallai theorem.

VERTEX CONNECTIVITY

κ(G) = min { |S| : S ⊂ V, G − S is disconnected or trivial }

κ(G) is the minimum number of vertices whose removal disconnects G (or reduces it to a single vertex). A graph is k-connected if κ(G) ≥ k. By convention, κ(Kₙ) = n − 1 for the complete graph.

WHITNEY'S INEQUALITY

κ(G) ≤ λ(G) ≤ δ(G)

Here λ(G) is the edge connectivity (minimum number of edges whose removal disconnects G) and δ(G) is the minimum vertex degree. Whitney's inequality tells us that vertex connectivity is the most restrictive measure, edge connectivity sits in between, and minimum degree provides an upper bound on both.

ℹ

Menger's Theorem

Menger's theorem provides a beautiful duality: the maximum number of internally vertex-disjoint paths between two non-adjacent vertices u and v equals the minimum number of vertices whose removal separates u from v. Equivalently, for edges: the maximum number of edge-disjoint u–v paths equals the minimum edge cut between u and v. This result connects the combinatorial notion of connectivity to the algorithmic problem of finding disjoint paths, and it underpins the max-flow min-cut theorem in network flow theory.

SECTION 5

Classifying Graphs by Connectivity & Cycle Structure

Graphs can be organized into a taxonomy based on their cycle structure and connectivity properties. At one extreme, trees are connected graphs with no cycles whatsoever — they are minimally connected, since removing any single edge disconnects them. At the other extreme, complete graphs Kₙ have the maximum possible degree for every vertex and achieve the highest connectivity κ(Kₙ) = n − 1. Between these poles lies a rich spectrum of graph families whose properties depend on how paths and cycles interweave.

Four graph families arranged from left to right by increasing connectivity. Trees are minimally connected (κ = 1) and acyclic. Cycle graphs are 2-connected. Regular graphs like the Petersen graph achieve κ = 3. Complete graphs Kₙ have the maximum possible connectivity κ = n − 1.

Graph Family	Edges \|E\|	Cycles?	κ(G)	Key Property
Tree on n vertices	n − 1	None	1	Unique path between every pair
Cycle Cₙ	n	One Hamiltonian cycle	2	2-connected, every vertex degree 2
k-Regular graph	kn/2	Multiple	≤ k	All vertices share the same degree
Complete Kₙ	n(n − 1)/2	Every possible cycle	n − 1	Maximum density and connectivity
Bipartite Kₘ,ₙ	m × n	Only even-length cycles	min(m, n)	No odd cycles; 2-colorable

Classification of graph families by edge count, cycle structure, and connectivity

SECTION 6

Worked Example — Analyzing a Graph's Properties

Consider the graph H with vertex set V = {1, 2, 3, 4, 5, 6} and edge set E = {{1,2}, {1,3}, {2,3}, {2,4}, {3,5}, {4,5}, {4,6}, {5,6}}. We will determine the degree sequence, verify the Handshaking Lemma, find a longest path, identify all cycles, and compute the vertex connectivity.

Complete Analysis of Graph H

1
Step 1 — Compute Vertex Degrees

List the edges incident to each vertex. Vertex 1 appears in edges {1,2} and {1,3}, so deg(1) = 2. Vertex 2 appears in {1,2}, {2,3}, {2,4}, giving deg(2) = 3. Vertex 3: {1,3}, {2,3}, {3,5} → deg(3) = 3. Vertex 4: {2,4}, {4,5}, {4,6} → deg(4) = 3. Vertex 5: {3,5}, {4,5}, {5,6} → deg(5) = 3. Vertex 6: {4,6}, {5,6} → deg(6) = 2.

Degree sequence: (2, 3, 3, 3, 3, 2)
2
Step 2 — Verify the Handshaking Lemma

Sum of all degrees: 2 + 3 + 3 + 3 + 3 + 2 = 16. The number of edges |E| = 8. Check: 2 × 8 = 16. ✓ The lemma is confirmed. Also note that there are four vertices of odd degree and two of even degree; since 4 is even, this is consistent with the corollary that the number of odd-degree vertices is always even.

Σ deg(v) = 16 = 2 × |E| ✓
3
Step 3 — Find a Longest Path

We attempt to find a Hamiltonian path (one that visits all 6 vertices). Try the sequence 1–2–4–6–5–3. Check adjacencies: {1,2} ∈ E ✓, {2,4} ∈ E ✓, {4,6} ∈ E ✓, {6,5} ∈ E ✓, {5,3} ∈ E ✓. All 6 vertices are visited exactly once, so this is a Hamiltonian path of length 5.

Hamiltonian path: 1 → 2 → 4 → 6 → 5 → 3 (length 5)
4
Step 4 — Identify Cycles

Enumerate distinct cycles. Triangle: 1–2–3–1 uses edges {1,2}, {2,3}, {1,3}. Another cycle: 2–4–5–3–2 uses {2,4}, {4,5}, {3,5}, {2,3}; this is a 4-cycle. Yet another: 4–5–6–4 uses {4,5}, {5,6}, {4,6}; this is a triangle. We can also find longer cycles by composing these: 1–2–4–5–3–1 is a 5-cycle using {1,2}, {2,4}, {4,5}, {3,5}, {1,3}. And 2–4–6–5–3–2 is a 5-cycle as well. The graph has multiple distinct cycles of lengths 3, 4, and 5.

Cycles found: 1–2–3–1 (C₃), 2–4–5–3–2 (C₄), 4–5–6–4 (C₃), plus 5-cycles
5
Step 5 — Determine Vertex Connectivity κ(H)

By Whitney's inequality, κ(H) ≤ δ(H) = 2. Can the graph be disconnected by removing one vertex? Removing vertex 1 leaves vertices {2,3,4,5,6} with edges {2,3}, {2,4}, {3,5}, {4,5}, {4,6}, {5,6} — still connected (e.g., 2–3–5–4–6). Removing vertex 6 leaves {1,2,3,4,5} with edges {1,2}, {1,3}, {2,3}, {2,4}, {3,5}, {4,5} — still connected. We can verify that removing any single vertex leaves a connected subgraph. Therefore κ(H) ≥ 2. Since δ(H) = 2, we have κ(H) ≤ 2. To confirm κ(H) = 2, we need a vertex cut of size 2: removing vertices 2 and 5 eliminates all edges connecting {1,3} to {4,6}, disconnecting the graph.

κ(H) = 2 — graph H is 2-connected but not 3-connected

SECTION 7

Strengths & Limitations of Connectivity Measures

Different connectivity measures capture different facets of graph robustness. Choosing the right measure depends on whether you are modeling the failure of nodes (vertex connectivity), the failure of links (edge connectivity), or simply whether a network is in one piece. Each measure has strengths in certain application domains and limitations in others.

Measure	Strengths	Limitations
Connected / Disconnected	Simple Boolean check; quick to compute via BFS/DFS in O(\|V\| + \|E\|); natural first question about any network.	Binary — offers no gradient of robustness. A tree and K₁₀₀ are both "connected" despite vastly different resilience.
Vertex connectivity κ(G)	Models node-failure scenarios (e.g., server crashes, router failures). Captures the worst-case vulnerability of the network.	NP-hard to compute for general k in certain formulations. Does not distinguish between different patterns of failure — treats all vertex removals equally.
Edge connectivity λ(G)	Models link failures (e.g., cut cables). Efficiently computable via max-flow algorithms in polynomial time.	Does not account for node heterogeneity — a backbone router failing has a larger effect than a peripheral link dropping.
Minimum degree δ(G)	Trivially computable in O(\|V\|). Provides an immediate upper bound on both κ and λ via Whitney's inequality.	A loose upper bound in many cases. A star graph K₁,ₙ₋₁ has δ = 1 and κ = 1, but a graph with δ = 5 could still have κ = 1.

Comparison of connectivity measures in graph theory

✦

KEY TAKEAWAY

Think of connectivity like structural engineering for a bridge. Asking "is the bridge in one piece?" is basic connectivity. Asking "how many support cables can fail before it collapses?" is edge connectivity. Asking "how many pillars can be removed before it falls?" is vertex connectivity. And measuring the thinnest pillar tells you the minimum degree — it bounds the others from above but doesn't guarantee anything by itself. Engineers and network architects choose the appropriate measure based on what component of the system is most likely to fail.

SECTION 8

Connection to Advanced Graph Theory

The ideas developed in this lesson serve as gateways to deeper areas of graph theory and combinatorics. Understanding degree constraints leads naturally into the study of Eulerian and Hamiltonian graph theory, where degree conditions determine the existence of special traversals. Cycle structure underpins planarity (Kuratowski's theorem characterizes non-planar graphs via subdivisions of K₅ and K₃,₃) and graph coloring (a graph is bipartite if and only if it contains no odd cycles). Connectivity generalizes into the theory of network flows and matroids.

This Lesson's Concept	Advanced Extension	Key Result
Vertex degree	Eulerian circuits	A connected graph has an Eulerian circuit iff every vertex has even degree (Euler, 1736).
Degree sequence	Hamiltonian cycles	Dirac's theorem: if n ≥ 3 and δ(G) ≥ n/2, then G is Hamiltonian.
Paths (shortest)	Network flow / routing	Dijkstra's and Bellman-Ford algorithms; max-flow min-cut theorem (Ford-Fulkerson).
Cycles (odd vs. even)	Graph coloring	A graph is 2-colorable (bipartite) iff it has no odd-length cycles.
k-Connectivity	Matroids & reliability	Whitney's matroid theory generalizes connectivity; reliability polynomials quantify failure probabilities.

How foundational concepts connect to advanced topics

As you progress through graph theory, you will find that nearly every theorem you encounter references degree, path, cycle, or connectivity in its hypotheses or conclusions. Mastering these four pillars now gives you the structural literacy to read and formulate graph-theoretic arguments with confidence.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Can a simple graph on 7 vertices have a degree sequence of (1, 2, 2, 3, 3, 3, 4)? Justify your answer using the Handshaking Lemma and any other necessary criteria.

Show answer

First, check the Handshaking Lemma: the sum of degrees is 1 + 2 + 2 + 3 + 3 + 3 + 4 = 18, which is even, so 18/2 = 9 edges are required. Since a simple graph on 7 vertices can have at most C(7,2) = 21 edges, and 9 ≤ 21, the edge count is feasible. The maximum degree is 4, which is at most n − 1 = 6, so no vertex exceeds the degree bound. The number of odd-degree vertices is 4 (the vertices of degree 1, 3, 3, 3), which is even — consistent. To fully verify, one can apply the Erdős–Gallai theorem: sort the sequence in non-increasing order as (4, 3, 3, 3, 2, 2, 1) and check the inequalities. The sequence is indeed graphical, so yes, such a graph exists.

Question 2: BASIC CALCULATION

A simple connected graph G has 8 vertices and 10 edges. What is the sum of all vertex degrees? What is the minimum possible value of the maximum degree Δ(G)?

Show answer

By the Handshaking Lemma, Σ deg(v) = 2 × 10 = 20. With 8 vertices sharing a total degree sum of 20, the average degree is 20/8 = 2.5. The maximum degree Δ(G) must be at least ⌈2.5⌉ = 3, since if every vertex had degree at most 2, the total degree would be at most 16 < 20. More carefully, if Δ(G) = 2, then every vertex has degree ≤ 2, and the graph would be a union of paths and cycles; a connected graph where every vertex has degree exactly 2 is a single cycle C₈ with 8 edges, not 10. So Δ(G) ≥ 3. A graph achieving Δ(G) = 3 exists — for example, the graph formed by C₈ plus two additional edges — so the minimum possible maximum degree is 3.

Question 3: INTERMEDIATE

Let G be a graph on vertices {a, b, c, d, e} with edges {a,b}, {a,c}, {b,c}, {b,d}, {c,d}, {d,e}. Find the vertex connectivity κ(G) and the edge connectivity λ(G). Verify Whitney's inequality κ(G) ≤ λ(G) ≤ δ(G).

Show answer

First compute degrees: deg(a) = 2, deg(b) = 3, deg(c) = 3, deg(d) = 3, deg(e) = 1. So δ(G) = 1 (vertex e). Since e has degree 1, removing the single edge {d,e} disconnects e from the rest, so λ(G) ≤ 1. Since the graph is connected, λ(G) ≥ 1, hence λ(G) = 1. For vertex connectivity, vertex d is the only neighbor of e, so removing d isolates e; thus κ(G) ≤ 1. Since G is connected, κ(G) ≥ 1, so κ(G) = 1. Whitney's inequality gives 1 ≤ 1 ≤ 1, which holds. Vertex d is a cut vertex, and edge {d,e} is a bridge. The subgraph induced by {a, b, c, d} is 2-connected, but the pendant vertex e reduces all global connectivity measures to 1.

Question 4: APPLIED

A university campus network has 12 buildings connected by underground fiber-optic cables. The network manager wants the network to remain fully operational even if any single cable is cut. What is the minimum edge connectivity λ(G) the network must have? If the current network is a tree, how many additional cables must be added at minimum to achieve this? Explain your reasoning.

Show answer

The requirement that the network survives any single cable failure means λ(G) ≥ 2 — i.e., the graph must be 2-edge-connected. A tree on 12 vertices has exactly 11 edges and λ = 1 (every edge is a bridge). To make a tree 2-edge-connected, every edge must lie on at least one cycle. The minimum number of edges that must be added equals the number of leaves divided by 2 (rounded up), because each added edge can 'cover' at most two leaf-incident bridges by creating a cycle. However, in general the problem depends on the tree's structure. A clean lower bound: a tree has at least 2 leaves (pendant vertices), and creating a single cycle through all leaves requires at least ⌈L/2⌉ additional edges where L is the number of leaves. For a path (worst case: 2 leaves), one additional edge (connecting the two endpoints) creates a single Hamiltonian cycle with λ = 2. For a star K₁,₁₁ (11 leaves), at least ⌈11/2⌉ = 6 edges must be added. In general, the answer depends on the tree topology, but the minimum over all trees on 12 vertices is 1 additional edge (when the tree is a path), and the maximum needed is 6 (when the tree is a star).

Question 5: CRITICAL THINKING

Prove that every connected graph G with n ≥ 2 vertices contains at least two vertices that are not cut vertices. (A cut vertex is one whose removal disconnects the graph.) Hint: consider a longest path in G.

Show answer

Let P = v₁v₂…vₖ be a longest path in G. We claim that v₁ and vₖ are not cut vertices. Suppose for contradiction that v₁ is a cut vertex. Then G − v₁ has at least two connected components. Let C be a component that does not contain v₂. Since G is connected, there exists a vertex u ∈ C that was adjacent to v₁ in G. Now u is not on the path P (since all neighbors of v₁ on P lie in the component containing v₂). Consider the walk u–v₁–v₂–…–vₖ. Since u ∉ V(P), this gives a path of length k, one longer than P, contradicting the maximality of P. (If u were adjacent to some vᵢ with i > 1, we would have a longer path or a cycle that allows extending P.) A symmetric argument shows vₖ is not a cut vertex. Since k ≥ 2 (as n ≥ 2 and G is connected), the endpoints v₁ and vₖ are distinct, giving at least two non-cut vertices. This result is a lemma often used in proving Whitney's theorem relating connectivity to internally disjoint paths.

SUMMARY

Lesson Summary

Summary

This lesson established the four foundational pillars of graph structure. The degree of a vertex counts its incident edges, and the Handshaking Lemma guarantees that the sum of all degrees equals twice the number of edges. A path is a sequence of distinct vertices connected by edges, while a cycle is a closed path returning to its starting vertex. Connectivity measures how resilient a graph is to the removal of vertices or edges, with Whitney's inequality κ(G) ≤ λ(G) ≤ δ(G) relating vertex connectivity, edge connectivity, and minimum degree.

We classified graph families along a spectrum from trees (acyclic, minimally connected) to complete graphs (maximally dense, κ = n − 1). Menger's theorem provides the deep duality between disjoint paths and separating sets, connecting these local structural notions to global algorithmic problems in network flow. These concepts form the essential vocabulary for every subsequent topic in graph theory — from Eulerian and Hamiltonian theory to graph coloring and planarity.