Admin: /* Key Theorems and Results */

2026-06-14T19:00:02Z

Key Theorems and Results

← Older revision		Revision as of 19:00, 14 June 2026
Line 146:		Line 146:
	==Key Theorems and Results==		==Key Theorems and Results==

	{\| class="wikitable"		{\| class="table wikitable"
	\|-		\|-
	! Result !! Statement		! Result !! Statement

Admin: Add Chapter 1 (Fundamental Concepts) reading notes (via create-page on MediaWiki MCP Server)

2026-06-14T18:55:20Z

Add Chapter 1 (Fundamental Concepts) reading notes (via create-page on MediaWiki MCP Server)

New page

'''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''' Pn, '''cycle''' Cn, '''complete graph''' Kn, '''complete bipartite graph''' (biclique) Kr,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''': Kn can be expressed as the union of k bipartite graphs if and only if n ≤ 2k.

===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''' Qk: vertices are binary k-tuples, edges join tuples differing in exactly one position. Qk is k-regular, bipartite, has 2k vertices and k·2k−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 ai,j = number of edges from vi to vj; 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 2n binary digits such that all 2n strings of length n are distinct. Constructed via Eulerian circuits in the '''de Bruijn graph''' Dn (vertices are binary (n−1)-tuples; edges correspond to overlapping n-tuples). '''Theorem 1.4.26''' proves Dn is Eulerian.

===Orientations and Tournaments===

* An '''orientation''' of a graph assigns a direction to each edge. A '''tournament''' is an orientation of Kn (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==

{| class="wikitable"
|-
! 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) || Dn is Eulerian; Eulerian circuits yield de Bruijn sequences
|}

=Flags=

{{ReadingFlag}}

Introduction to Graph Theory/Fundamental Concepts - Revision history

Admin: /* Key Theorems and Results */

Admin: Add Chapter 1 (Fundamental Concepts) reading notes (via create-page on MediaWiki MCP Server)