Graph Theory Tutorial
Learn Graph Theory step by step: 36 lessons in 9 chapters with examples, quizzes, diagrams and projects.
Start learning →
of lessons completed
Getting Started
- What Is a Graph? Meet graphs in graph theory: vertices, edges, and why dots-and-lines models road maps, friendships and networks. Build your first graph in Python and answer simple questions.
- Graph Terminology Learn the core vocabulary of graph theory: degree, neighbors, isolated vertices, regular graphs and the handshake lemma, with runnable Python examples that check each rule.
- Kinds of Graphs Tour the main kinds of graphs: simple, directed, weighted, multigraphs, complete, bipartite, paths, cycles and trees, with Python checks for each property.
- The Seven Bridges of Königsberg Follow the puzzle that started graph theory: Euler's solution to the Königsberg bridges, Euler paths and circuits, and a Python check that proves no walk crosses each bridge once.
Graphs and Representations
- The Adjacency Matrix Represent a graph as an adjacency matrix: build it in Python and NumPy, read degrees from rows, handle directed and weighted graphs, and count walks with matrix powers.
- The Adjacency List Learn the adjacency list, the standard sparse-graph representation: build it with dictionaries and sets in Python, store weights and directions, and compare memory against matrices.
- Edge Lists and Incidence Matrices Two more graph representations: the edge list, ideal for files and sorting, and the incidence matrix, ideal for algebra. Convert between all four forms with Python and NumPy.
- Building a Graph Class Write a reusable Graph class in Python with add, remove, degree, neighbors and iteration methods for directed or undirected weighted graphs, then compare it with networkx.
- Subgraphs and Isomorphism Understand subgraphs, induced subgraphs, complements and graph isomorphism: decide when two drawings are the same graph, with invariants, brute force search and networkx checks.
Connectivity and Paths
- Walks, Paths and Cycles Learn the difference between walks, trails, paths and cycles, what connected means, how distance, diameter and girth are defined, and compute them in Python.
- Breadth-First Search Learn breadth-first search step by step: the queue-based algorithm, shortest paths in unweighted graphs, level structure, path reconstruction and O(n + m) running time, in Python.
- Depth-First Search Learn depth-first search: recursive and iterative Python versions, discovery and finish times, edge classification, cycle detection and topological sorting of directed acyclic graphs.
- Connected Components and Cuts Find connected components with BFS and union-find, locate bridges and articulation points with a DFS low-link algorithm, and compute strongly connected components in directed graphs.
- Dijkstra and Shortest Paths Compute shortest paths in weighted graphs with Dijkstra's algorithm and a heap, reconstruct routes, see why negative weights break it, and meet Bellman-Ford and Floyd-Warshall.
Trees and Spanning Trees
- Trees and Forests Learn what a tree is in graph theory: equivalent definitions, the n-1 edge rule, leaves, forests, rooted trees, center and diameter, with Python code that checks each property.
- Minimum Spanning Trees Find the cheapest way to connect a weighted graph: spanning trees, the cut and cycle properties, Kruskal's algorithm with union-find and Prim's algorithm with a heap, checked in Python.
- Prüfer Codes and Cayley's Formula Encode every labeled tree as a short Prüfer sequence and decode it back, then use the bijection to prove Cayley's formula n^(n-2) for counting labeled trees, verified in Python.
- The Matrix-Tree Theorem Count the spanning trees of any graph with a determinant: build the Laplacian matrix, apply Kirchhoff's matrix-tree theorem, and check it against Cayley's formula and brute force in Python.
Coloring and Matching
- Graph Coloring Basics Learn what a proper graph coloring is, how the chromatic number is defined, how to test k-colorability with backtracking, and why bipartite graphs need only two colors.
- Greedy Coloring and Brooks' Theorem Color graphs fast with the greedy algorithm, compare vertex orderings (Welsh-Powell, smallest-last, DSATUR) and learn the degree bounds that Brooks' theorem gives.
- Edge Coloring and the Chromatic Polynomial Color the edges of a graph, learn Vizing's theorem and Konig's edge coloring theorem, and count proper colorings with the chromatic polynomial and deletion-contraction.
- Bipartite Matching and Augmenting Paths Understand matchings, Berge's augmenting path theorem and build Kuhn's and Hopcroft-Karp algorithms in Python to pair workers with jobs, checked against SciPy.
- Hall's Theorem, König's Theorem and Stable Matching When does a perfect matching exist? Learn Hall's condition, König's min vertex cover theorem, and the Gale-Shapley stable matching algorithm with runnable Python examples.
Planarity and Flows
- Planar Graphs and Euler's Formula Learn what makes a graph planar, trace faces of an embedding in Python, prove edge bounds from Euler's formula and see why planar graphs are 6-colorable.
- Kuratowski's Theorem and Planarity Checking Learn Kuratowski's and Wagner's theorems, graph minors and subdivisions, and test planarity in Python with rotation systems and a K5/K3,3 minor search.
- Maximum Flow and the Ford-Fulkerson Method Understand flow networks, residual graphs and augmenting paths, then implement Ford-Fulkerson and Edmonds-Karp in Python and verify them against SciPy's maximum_flow.
- Minimum Cuts and Flow Applications Learn s-t cuts, the max-flow min-cut theorem, how to extract a minimum cut from the residual graph, and apply flows to matching and edge-disjoint paths with Python.
Spectral Graph Theory
- Graph Matrices and the Spectrum Turn graphs into matrices: count walks and triangles with adjacency powers, read eigenvalues of cycles, complete and bipartite graphs, and meet cospectral graphs in NumPy.
- The Laplacian and the Fiedler Vector Learn the graph Laplacian L = D - A, why its eigenvalues count components, how algebraic connectivity measures robustness, and bisect graphs with the Fiedler vector.
- Spectral Clustering and Random Walks Cluster a graph with Laplacian eigenvectors and k-means, see how random walks converge to degree-proportional distributions, and compute PageRank by power iteration.
Applications
- Centrality Measures in Networks Find the most important vertices in a network: implement degree, closeness, betweenness (Brandes) and eigenvector centrality in Python and learn when each one is the right tool.
- Scheduling and Timetabling with Coloring Apply graph coloring to real scheduling: build conflict graphs for exam timetables, add capacity limits, color interval graphs optimally and see register allocation as coloring.
- Network Models: Small Worlds and Scale-Free Graphs Generate and measure Erdos-Renyi, Watts-Strogatz small-world and Barabasi-Albert scale-free graphs in Python: giant components, clustering, path lengths and degree distributions.
Projects and Practice
- Project: Campus Timetable Scheduler Build a complete exam timetable scheduler in Python: conflict graph, DSATUR, iterated greedy improvement, clique lower bound, room capacities and a validator, step by step.
- Project: Volunteer Shift Planner with Max Flow Build a shift planner with maximum flow: model volunteers and shifts as a network, find assignments, diagnose shortages with a minimum cut and verify the result with SciPy.
- Graph Theory Practice Problems Eight graph theory exercises with worked, runnable solutions: degree sequences, two-team splits, domino tilings, edge connectivity, Mycielski graphs, planarity bounds and Laplacian components.