Skip to content
Tutorials Center
My learning

Topics

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

  1. 1 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.
  2. 2 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.
  3. 3 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.
  4. 4 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

  1. 5 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.
  2. 6 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.
  3. 7 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.
  4. 8 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.
  5. 9 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

  1. 10 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.
  2. 11 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.
  3. 12 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.
  4. 13 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.
  5. 14 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

  1. 15 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.
  2. 16 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.
  3. 17 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.
  4. 18 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

  1. 19 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.
  2. 20 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.
  3. 21 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.
  4. 22 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.
  5. 23 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

  1. 24 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.
  2. 25 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.
  3. 26 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.
  4. 27 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

  1. 28 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.
  2. 29 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.
  3. 30 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

  1. 31 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.
  2. 32 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.
  3. 33 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

  1. 34 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.
  2. 35 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.
  3. 36 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.