Chapter 1: Fundamental Concepts

Source: Introduction to Graph Theory, 2nd Edition, by Douglas B. West

Overview

Chapter 1 lays the groundwork for the entire text by introducing the basic definitions, proof techniques, and structural results of graph theory. It is divided into four sections covering graphs, paths and cycles, vertex degrees and counting, and directed graphs.

1.1 What Is a Graph?

The Definition

The chapter opens with the Königsberg Bridge Problem (1736) as the motivating example for graph theory. The citizens of Königsberg wondered whether they could cross all seven bridges exactly once and return home — Euler showed this was impossible.

A graph G is defined as a triple consisting of a vertex set V(G), an edge set E(G), and a relation associating each edge with two endpoints. A loop is an edge whose endpoints are equal; multiple edges share the same pair of endpoints. A simple graph has no loops or multiple edges.

Key terminology introduced: adjacent vertices, neighbors, finite graphs.

Graphs as Models

Several motivating applications are presented:

Acquaintance relations — modeling social networks with vertices for people and edges for acquaintance, introducing complement, clique, and independent set.
Job assignments and bipartite graphs — modeling people-to-jobs assignments, introducing bipartite graphs (vertex set partitioned into two independent sets).
Scheduling and graph coloring — the chromatic number χ(G), the minimum number of colors needed so adjacent vertices receive different colors; k-partite graphs.
Maps and coloring — the Four Color Problem, introducing planar graphs.
Routes in road networks — introducing path (vertices ordered so consecutive ones are adjacent) and cycle (vertices on a circle with consecutive adjacency).
Subgraph (H ⊆ G with the same edge-endpoint assignments) and connected graphs (every pair of vertices joined by a path).

Matrices and Isomorphism

The adjacency matrix A(G) records edge counts between vertex pairs; the incidence matrix M(G) records which vertices are endpoints of which edges. The degree of a vertex is the number of incident edges.
An isomorphism from G to H is a bijection f: V(G) → V(H) preserving adjacency. The isomorphism relation is shown to be an equivalence relation (reflexive, symmetric, transitive), partitioning graphs into isomorphism classes.
Standard named graphs: path P_n, cycle C_n, complete graph K_n, complete bipartite graph (biclique) K_r,s.
Counting: the number of simple graphs on a fixed vertex set of size n is 2^{(n choose 2)}.

Decomposition and Special Graphs

A graph is self-complementary if it is isomorphic to its complement. A decomposition partitions the edge set into subgraphs.
The Petersen graph is formally defined as the graph whose vertices are the 2-element subsets of a 5-element set, with edges between disjoint subsets. It is 3-regular, has girth 5, and 120 automorphisms. It serves as a key example and counterexample throughout the book.
Girth: length of the shortest cycle.
Automorphism: an isomorphism from G to itself. Vertex-transitive graphs have an automorphism mapping any vertex to any other.

1.2 Paths, Cycles, and Trails

Induction

The section begins by reviewing strong induction (the Strong Principle of Induction), a key proof technique used throughout graph theory.

Connection in Graphs

A walk is a sequence of alternating vertices and edges; a trail has no repeated edges; a path has no repeated vertices. Walks/trails/paths can be closed (same first and last vertex).
Lemma 1.2.5: Every u,v-walk contains a u,v-path (proved by induction — if a vertex repeats, shortcut it).
A graph is connected if every pair of vertices has a path between them. The connection relation is an equivalence relation; its classes define the components of G. An isolated vertex has degree 0.
Proposition 1.2.11: A graph with n vertices and k edges has at least n − k components.

Cut-edges, Cut-vertices, and Induced Subgraphs

A cut-edge or cut-vertex is an edge or vertex whose deletion increases the number of components.
An induced subgraph G[T] consists of a vertex subset T and all edges of G with both endpoints in T.
Theorem 1.2.14: An edge is a cut-edge if and only if it belongs to no cycle.

Bipartite Graphs

Lemma 1.2.15: Every closed odd walk contains an odd cycle.
Theorem 1.2.18 (König, 1936): A graph is bipartite if and only if it has no odd cycle. Proved by constructing a bipartition using shortest-path distances from a chosen vertex in each component.
Theorem 1.2.23: K_n can be expressed as the union of k bipartite graphs if and only if n ≤ 2^k.

Eulerian Circuits

A graph is Eulerian if it has a closed trail containing all edges. An Eulerian circuit is such a closed trail.
Theorem 1.2.26: A graph is Eulerian if and only if it has at most one nontrivial component and all vertices have even degree. The proof uses induction on the number of edges and the technique of extremality (choosing a maximal path/trail).
Proposition 1.2.27: Every even graph decomposes into cycles.
The TONCAS principle: "The Obvious Necessary Conditions Are Also Sufficient."
Proposition 1.2.28: A simple graph where every vertex has degree ≥ k contains a path of length ≥ k, and if k ≥ 2, a cycle of length ≥ k + 1.
Theorem 1.2.33: A connected graph with exactly 2k odd vertices can be decomposed into max{k, 1} trails.

1.3 Vertex Degrees and Counting

Counting and Bijections

Order n(G) = |V(G)|; size e(G) = |E(G)|.
Degree-Sum Formula (Proposition 1.3.3, "Handshaking Lemma"): Σ d(v) = 2e(G). Immediate corollaries: every graph has an even number of odd-degree vertices; no graph of odd order is regular; a k-regular graph on n vertices has nk/2 edges.
The k-dimensional hypercube Q_k: vertices are binary k-tuples, edges join tuples differing in exactly one position. Q_k is k-regular, bipartite, has 2^k vertices and k·2^k−1 edges.
Proposition 1.3.9: A k-regular bipartite graph (k > 0) has equal-sized partite sets.
Petersen graph properties: it has exactly ten 6-cycles (established via a bijection with claws).
Vertex-deleted subgraphs and the Reconstruction Conjecture (Kelly–Ulam, 1942): a simple graph with ≥ 3 vertices is uniquely determined by its list of vertex-deleted subgraphs (still open).

Extremal Problems

Proposition 1.3.13: The minimum number of edges in a connected n-vertex graph is n − 1.
Proposition 1.3.15: If δ(G) ≥ (n−1)/2 for a simple n-vertex graph, then G is connected. This bound is sharp (Example 1.3.16: K_⌊n/2⌋ + K_⌈n/2⌉).
Disjoint union G + H and the notation mG for m disjoint copies.
Theorem 1.3.19: Every loopless graph has a bipartite subgraph with at least e(G)/2 edges (proved by an algorithmic/switching argument).
Theorem 1.3.23 (Mantel, 1907): The maximum number of edges in a triangle-free simple graph on n vertices is ⌊n²/4⌋, achieved by K_{⌊n/2⌋,⌈n/2⌉}.
The induction trap (Example 1.3.24): a cautionary example showing how induction proofs can go wrong when the induction step doesn't cover all instances.
Remark 1.3.25: A general template for induction proofs in graph theory — from G obtain a smaller G', apply the induction hypothesis, then lift the conclusion back to G.

Graphic Sequences

A degree sequence lists vertex degrees in nonincreasing order. A list is graphic if it is the degree sequence of some simple graph.
Proposition 1.3.28: A list of nonneg integers is realizable as vertex degrees (allowing loops/multi-edges) iff the sum is even.
Theorem 1.3.31 (Erdős–Gallai / Havel–Hakimi): A list d of n > 1 integers is graphic iff d' is graphic, where d' is obtained by deleting the largest element Δ and subtracting 1 from the next Δ largest entries. This yields a recursive algorithm.
2-switches (swapping edges xy, zw for xz, yw) preserve degree sequences.
Theorem 1.3.33 (Berge): Two simple graphs on the same vertex set have the same degree sequence iff one can be transformed into the other by a sequence of 2-switches.

1.4 Directed Graphs

Definitions and Examples

A directed graph (digraph) has edges that are ordered pairs; each edge goes from its tail to its head. Loops and multiple edges are defined analogously.
A successor of u is a vertex v with edge u → v; a predecessor has edge v → u.
Applications: finite state machines (transitions between states), Markov chains (transition probabilities), functional digraphs (iterating a function f: A → A).
The underlying graph of a digraph is obtained by dropping edge orientations.
Adjacency and incidence matrices for digraphs: A(G) has entry a_i,j = number of edges from v_i to v_j; M(G) uses +1 for tails and −1 for heads.
Weakly connected: underlying graph is connected. Strongly connected: a directed path exists for every ordered pair of vertices. Strong components are maximal strongly connected subdigraphs.
Kernels: an independent set S ⊆ V(D) such that every vertex outside S has a successor in S. Theorem 1.4.16 (Richardson): Every digraph with no odd cycle has a kernel.

Vertex Degrees

Outdegree d⁺(v) and indegree d⁻(v). The degree-sum formula becomes: Σ d⁺(v) = e(G) = Σ d⁻(v).
Degree pairs (d⁺, d⁻) and their realizability.
The split of a digraph D is a bipartite graph with two copies of V(D), useful for translating digraph questions into bipartite graph questions.

Eulerian Digraphs

Theorem 1.4.24: A digraph is Eulerian if and only if d⁺(v) = d⁻(v) for each vertex and the underlying graph has at most one nontrivial component.
De Bruijn cycles (Application 1.4.25): A cyclic arrangement of 2ⁿ binary digits such that all 2ⁿ strings of length n are distinct. Constructed via Eulerian circuits in the de Bruijn graph D_n (vertices are binary (n−1)-tuples; edges correspond to overlapping n-tuples). Theorem 1.4.26 proves D_n is Eulerian.

Orientations and Tournaments

An orientation of a graph assigns a direction to each edge. A tournament is an orientation of K_n (models round-robin competitions).
The score sequence of a tournament lists the outdegrees.
A king in a digraph is a vertex from which every other vertex is reachable by a path of length at most 2.
Proposition 1.4.30 (Landau, 1953): Every tournament has a king (proved by extremality — the vertex of maximum outdegree is always a king).

Key Proof Techniques Introduced

Induction (strong induction) — the primary proof framework
Extremality — choosing a maximal/minimal object to extract useful structural information
Counting two ways — the degree-sum formula paradigm
Algorithmic/constructive proofs — proving existence by exhibiting an algorithm
TONCAS — recognizing when obvious necessary conditions are also sufficient
The induction trap — a warning about incomplete induction steps

Key Theorems and Results

Result	Statement
Degree-Sum Formula (1.3.3)	Σ d(v) = 2e(G)
König (1.2.18)	G is bipartite ⟺ G has no odd cycle
Euler (1.2.26)	G is Eulerian ⟺ at most one nontrivial component and all degrees even
Mantel (1.3.23)	Max edges in triangle-free graph on n vertices = ⌊n²/4⌋
Havel–Hakimi (1.3.31)	Recursive characterization of graphic sequences
Berge (1.3.33)	Same degree sequence ⟺ connected by 2-switches
Richardson (1.4.16)	No odd cycle ⟹ digraph has a kernel
Landau (1.4.30)	Every tournament has a king
De Bruijn (1.4.26)	D_n is Eulerian; Eulerian circuits yield de Bruijn sequences

Flags

Introduction to Graph Theory/Fundamental Concepts

From charlesreid1

Contents