Skip to content

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.

10 chapters · 28 sectionsEN · 繁 · 简
My course notes

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.

Open this course in the knowledge map

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.

Open this course in the knowledge map

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.1

    Trees and connectivity

    Paths, bridges, spanning trees and the edge count of a finite tree.

  2. 1.2

    Bipartite coloring and odd-cycle certificates

    Prove the odd-cycle criterion and construct either a coloring or an obstruction.

  3. 1.3

    Fundamental cycles and even edge sets

    Build the cycle space from a spanning forest and count its elements.

  4. 1.4

    Distances, diameters, and tree centers

    Prove the tree-center theorem and justify simultaneous leaf pruning.

  5. 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.

  6. 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

  1. 2.1

    Eulerian circuits and parity

    Prove the even-degree criterion for a closed trail using cycle splicing.

  2. 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

  1. 3.1

    Planar graphs, Euler's formula and coloring

    Count faces in a plane embedding and use the resulting bounds to prove nonplanarity.

  2. 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

  1. 4.1

    Hamiltonian cycles and degree conditions

    Prove degree-based sufficient conditions while distinguishing them from necessary conditions.

  2. 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

  1. 5.1

    Directed graphs, reachability and Euler circuits

    Distinguish weak and strong connectivity and prove the directed Euler criterion.

  2. 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

  1. 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.

  2. 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

  1. 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

  1. 8.1

    Graph representations and isomorphism

    Represent finite graphs, verify isomorphisms and count walks using adjacency matrices.

  2. 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

  1. 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.

  2. 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.

  3. 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

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. 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.

Vercel visit statistics and public-page performance measurements each require separate consent. Neither is needed to use the website.

Website function storage (used when needed)

Security, sign-in and your chosen preferences use storage when needed. This is separate from optional statistics.

Withdrawing stops future statistics. The page reloads if analytics code needs unloading. It does not delete data already sent.

Read Cookie and storage details