maths.free › Combinatorics & Graph Theory

Combinatorics & Graph Theory

Counting, generating functions, graphs, trees, colourings and networks.

Lessons

Introductory The counting principles Product rule, sum rule, permutations, combinations, and when each applies. 5 choose 2 Core Pigeonhole principle and inclusion, exclusion Two counting ideas that prove things without listing anything. {1,2,3,4} union {3,4,5,6} Core Binomial coefficients and Pascal's triangle Identities, the binomial theorem, and combinatorial proofs. expand (a + b)^6 Core Recurrences and generating functions Solving recurrence relations, and encoding a sequence as a power series. fib(25) Introductory Graphs: vertices, edges, degrees The basic objects of graph theory and the handshake lemma. sum of k for k = 1 to 5 Core Paths, cycles, trees, Euler and Hamilton Connectivity, spanning trees, Euler circuits and the bridges of Königsberg. 5 choose 2 Core Colouring and planar graphs Chromatic number, Euler's formula V − E + F = 2, and the four-colour theorem. 6 - 2

How many, and how connected. Counting arguments that turn into generating functions, and graphs (dots and lines) that model everything from road networks to molecules.

More lessons

An Introduction to Combinatorics

Introduction Enumeration Combinatorics and Graph Theory Combinatorics and Number Theory Combinatorics and Geometry Combinatorics and Optimization Sudoku Puzzles Discussion

Strings, Sets, and Binomial Coefficients

Strings: A First Look Permutations Combinations The Ubiquitous Nature of Binomial Coefficients The Binomial Theorem Multinomial Coefficients Discussion An Activity on Lattice Paths, the Binomial Theorem, and the Multinomial Theorem

Induction

Introduction The Positive Integers are Well Ordered The Meaning of Statements Binomial Coefficients Revisited Solving Combinatorial Problems Recursively Mathematical Induction Inductive Definitions Proofs by Induction Strong Induction Discussion

Combinatorial Basics

The Pigeon Hole Principle An Introduction to Complexity Theory The Big Oh and Little Oh Notations Exact Versus Approximate Discussion

Partially Ordered Sets

Basic Notation and Terminology Additional Concepts for Posets Dilworth's Chain Covering Theorem and its Dual Linear Extensions of Partially Ordered Sets The Subset Lattice Interval Orders Finding a Representation of an Interval Order Dilworth's Theorem for Interval Orders Discussion

Inclusion-Exclusion

Introduction The Inclusion-Exclusion Formula Enumerating Surjections Derangements The Euler \phi Function Discussion An Activity to Enumerate Surjections

Generating Functions

Basic Notation and Terminology Another look at distributing apples or folders Newton's Binomial Theorem An Application of the Binomial Theorem Partitions of an Integer Exponential generating functions Discussion

Recurrence Equations

Introduction Linear Recurrence Equations Advancement Operators Solving advancement operator equations Formalizing our approach to recurrence equations Using generating functions to solve recurrences Solving a nonlinear recurrence Discussion

Graph Algorithms

Minimum Weight Spanning Trees Digraphs Dijkstra's Algorithm for Shortest Paths Historical Notes

Network Flows

Basic Notation and Terminology Flows and Cuts Augmenting Paths The Ford-Fulkerson Labeling Algorithm A Concrete Example Integer Solutions of Linear Programming Problems

Combinatorial Applications of Network Flows

Introduction Matchings in Bipartite Graphs Chain partitioning

Pólya's Enumeration Theorem

Coloring the Vertices of a Square Permutation Groups Burnside's Lemma Pólya's Theorem Applications of Pólya's Enumeration Formula

The Many Faces of Combinatorics

On-line algorithms Extremal Set Theory Markov Chains The Stable Matching Theorem ZeroOne Matrices Arithmetic Combinatorics The Lovász Local Lemma Applying the Local Lemma

Graphs

Graph theory Graph (discrete mathematics)Degree (graph theory)Path (graph theory)Cycle (graph theory)Tree (graph theory)Spanning tree Connectivity (graph theory)Bipartite graph Planar graph Graph coloring Four color theorem Eulerian path Hamiltonian path Matching (graph theory)Adjacency matrix Shortest path problem Maximum flow problem

Deeper

Ramsey theory Extremal graph theory Probabilistic method Design theory Latin square Combinatorial optimization

Some of these lessons are adapted from open texts: Keller & Trotter, Applied Combinatorics, Levin, Discrete Mathematics: An Open Introduction, OpenStax Contemporary Mathematics, Wikipedia. Each lesson page names its source and licence.

Symbols used here

Tap any symbol for the full definition, a picture, and what every letter in it means.

Questions people ask

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges), not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

Have a problem of your own?
Type it or draw it on the solver page: every step, a picture, the answer hidden until you ask. Solve →

Other branches

＋ Arithmetic 𝑥 Algebra △ Geometry ∿ Trigonometry ƒ Precalculus σ Statistics & Probability ⊢ Discrete Math & Logic ∫ Calculus ⊞ Linear Algebra ℕ Number Theory ẏ Differential Equations ∇ Multivariable Calculus ε Real Analysis ∈ Set Theory & Logic 𝔾 Abstract Algebra 𝑃 Probability Theory ≈ Numerical Methods ℂ Complex Analysis ◎ Topology μ Measure Theory ‖·‖ Functional Analysis κ Differential Geometry π₁ Algebraic Topology → Category Theory ∂ Partial Differential Equations ≋ Fluid Dynamics ∞ Frontiers