MATH3260
Graph Theory
Trees and connectivity, Eulerian and Hamiltonian graphs, planarity and coloring, directed graphs, matchings, flows and cuts, and extremal graph theory, with proofs and worked examples.
Your progress
0/ 28 sections marked complete
Next section: Trees and connectivity
Completion marks are saved in this browser.
This course in the web
In the MATH3260 notes
- Theorem cards
- 90
- Definitions
- 56
- Counterexamples
- 32
- Concept lenses
- 20
- Histories of ideas
- 0
- Proof X-rays
- 30
No concept lens from this course is recorded in the web yet.
Counts cover the 28 public sections of this course and what is written in them, not recorded connections. 0 of these sections are indexed into the web in detail so far.
In the webTheorem cards 90 · Definitions 56 · Counterexamples 32 · Concept lenses 20 · Proof X-rays 30
No concept lens from this course is recorded in the web yet.
Counts cover the 28 public sections of this course and what is written in them, not recorded connections. 0 of these sections are indexed into the web in detail so far.
Chapter 1 · 6 sections
Trees and connectivity
Paths, bridges, spanning trees and the edge count of a finite tree.
Theorems 24 · Definitions 13Counterexamples 8Lenses 4Proof X-rays 7
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 1.1
Trees and connectivity
Paths, bridges, spanning trees and the edge count of a finite tree.
- 1.2
Bipartite coloring and odd-cycle certificates
Prove the odd-cycle criterion and construct either a coloring or an obstruction.
- 1.3
Fundamental cycles and even edge sets
Build the cycle space from a spanning forest and count its elements.
- 1.4
Distances, diameters, and tree centers
Prove the tree-center theorem and justify simultaneous leaf pruning.
- 1.5
Prüfer Encoding of Labeled Trees and Cayley's Formula
A self-contained chapter on Prüfer codes. It defines the encoding and decoding algorithms with explicit invariants, proves that they are mutually inverse, and derives Cayley's formula and the degree-sequence count.
- 1.6
Weighted Laplacians and spanning-tree enumeration
Prove the weighted matrix–tree formula from incidence minors, compute complete and multipartite tree counts, and derive exact edge-inclusion probabilities and deletion–contraction identities.
Chapter 2 · 2 sections
Eulerian traversal
Prove the even-degree criterion for a closed trail using cycle splicing.
Theorems 5 · Definitions 2Counterexamples 1Lenses 1Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 2.1
Eulerian circuits and parity
Prove the even-degree criterion for a closed trail using cycle splicing.
- 2.2
Euler trails and circuit construction
Extend Euler trail criteria and the splicing construction to finite undirected multigraphs, including loops and parallel edges.
Chapter 3 · 2 sections
Planarity and coloring
Count faces in a plane embedding and use the resulting bounds to prove nonplanarity.
Theorems 6 · Definitions 5Counterexamples 3Lenses 1Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 3.1
Planar graphs, Euler's formula and coloring
Count faces in a plane embedding and use the resulting bounds to prove nonplanarity.
- 3.2
Subdivisions and nonplanarity certificates
Recognize subdivisions and justify nonplanarity certificates.
Chapter 4 · 2 sections
Hamiltonian conditions
Prove degree-based sufficient conditions while distinguishing them from necessary conditions.
Theorems 6 · Definitions 3Counterexamples 2Lenses 1Proof X-rays 3
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 4.1
Hamiltonian cycles and degree conditions
Prove degree-based sufficient conditions while distinguishing them from necessary conditions.
- 4.2
Hamiltonian closure and degree-sequence certificates
Prove the degree-sum edge-addition lemma, order-independent closure and the full monotone degree-sequence condition, with constructive cycle recovery and explicit limits of negative tests.
Chapter 5 · 2 sections
Directed graphs
Distinguish weak and strong connectivity and prove the directed Euler criterion.
Theorems 9 · Definitions 5Counterexamples 3Lenses 1Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 5.1
Directed graphs, reachability and Euler circuits
Distinguish weak and strong connectivity and prove the directed Euler criterion.
- 5.2
Tournaments and directed paths
Construct directed Hamiltonian paths and understand cycles and reachability in tournaments.
Chapter 6 · 2 sections
Matchings
Prove matching optimality by alternating paths, derive Hall's condition, and construct a minimum vertex cover from the same search.
Theorems 6 · Definitions 3Counterexamples 2Lenses 2Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 6.1
Augmenting paths, Hall's theorem and König's theorem
Prove matching optimality by alternating paths, derive Hall's condition, and construct a minimum vertex cover from the same search.
- 6.2
Odd components, Tutte's condition and matching deficiency
Prove the general perfect-matching criterion through a saturated obstruction, derive the exact unmatched-vertex formula, and explain why odd components replace bipartite neighborhoods.
Chapter 7 · 1 section
Flows and cuts
Prove augmenting-flow correctness and integral max-flow min-cut, interpret reverse residual arcs, and recover bipartite matching and cover certificates.
Theorems 3 · Definitions 2Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 7.1
Residual paths, integral flows and minimum cuts
Prove augmenting-flow correctness and integral max-flow min-cut, interpret reverse residual arcs, and recover bipartite matching and cover certificates.
Chapter 8 · 2 sections
Graph representations
Represent finite simple graphs and compare them under relabeling.
Theorems 6 · Definitions 7Counterexamples 3Lenses 1Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 8.1
Graph representations and isomorphism
Represent finite graphs, verify isomorphisms and count walks using adjacency matrices.
- 8.2
Graphical Degree Sequences and the Havel–Hakimi Theorem
When a finite list of integers is the degree list of a simple graph on labeled vertices, with a complete proof of the Havel–Hakimi theorem and its realization algorithm.
Chapter 9 · 3 sections
Connectivity
Blocks, cut vertices and Menger-type connectivity theorems.
Theorems 8 · Definitions 8Counterexamples 3Lenses 2Proof X-rays 3
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 9.1
Blocks and the block–cut forest
Organize cut vertices and their overlapping resilient pieces into a forest that records every single-vertex separation.
- 9.2
Edge and vertex connectivity through Menger's theorem
Use integral flows to prove both finite undirected path–separator equalities, with cancellation, flow decomposition and the nonadjacent-endpoint hypothesis made explicit.
- 9.3
Global vertex connectivity and the fan lemma
Extend the nonadjacent-endpoint Menger theorem to all pairs in a k-connected graph, prove the fan lemma and its converse, and distinguish degree, edge and vertex resilience.
Chapter 10 · 6 sections
Coloring and extremal graph theory
Chromatic polynomials, edge coloring, Ramsey and Turán-type results.
Theorems 17 · Definitions 8Counterexamples 6Lenses 6Proof X-rays 6
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 10.1
Chromatic polynomials and deletion–contraction
Count proper colorings by inclusion–exclusion and deletion–contraction, prove tree/cycle and cut-vertex formulas, and read edges and triangles from polynomial coefficients.
- 10.2
Bipartite edge colors and alternating repairs
Prove the sharp degree bound for bipartite edge coloring by both regular completion and a constructive two-color repair, including parallel edges, runtime and odd-cycle obstructions.
- 10.3
Fans, two-color repairs and the general edge-coloring bound
Prove that every finite simple graph has an edge coloring with at most one color beyond maximum degree, using a complete fan invariant, alternating-path case analysis and explicit implementation costs.
- 10.4
Degeneracy, contraction and five planar colors
Prove degeneracy-order coloring, obtain a linear six-color construction for planar graphs, and prove the five-color theorem by contracting two nonadjacent neighbors.
- 10.5
Finite Ramsey bounds and random colorings
Prove finite two-color and multicolor clique guarantees, the exact triangle threshold, and first-moment lower bounds, while separating universal guarantees from existence and sufficient probability tests.
- 10.6
Clique-free extremal graphs and balanced parts
Prove the exact integer edge threshold for excluding a clique, including the full equality classification, and transfer it to minimum-edge graphs with bounded independence number.