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.
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.
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
Path
Cycle
Connectivity
The Handshaking Lemma
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.
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.
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.
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.
| 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 |
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.
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. |
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. |
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.
Practice Problems
Lesson 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.