Graph Theory

Explore graph structures; paths, coloring and planarity; networks and spectral viewpoints. Concepts and connections are available independently of video coverage.

Graph structures

Graphs
Vertices and edges model connections, with directed and undirected variants.
Video explanations to be added
Vertex degrees
Degree counts incident edge ends; directed graphs distinguish incoming and outgoing degrees.
Video explanations to be added
Graph connectivity
Paths determine connected components; vertex and edge connectivity quantify robustness to removal.
Video explanations to be added
Trees
A finite undirected tree is connected and has no cycles.
Video explanations to be added

Paths, coloring and planarity

Euler and Hamilton paths
Euler paths traverse each edge once; Hamilton paths visit each vertex once.
Video explanations to be added
Shortest path models
Dijkstra solves non-negative networks; Bellman-Ford tolerates negative edges and underpins route pricing.
4 reviewed resources
Graph coloring
Proper vertex coloring assigns different colors to adjacent vertices.
Video explanations to be added
Planar graphs
A planar graph can be drawn without edge crossings except at shared endpoints.
Video explanations to be added

Networks and spectral viewpoints

Graph matchings
A matching is a set of edges with no shared endpoints.
Video explanations to be added
Bipartite matching
Matching in a two-part graph pairs vertices across parts without shared endpoints.
Video explanations to be added
Network flow models
Maximise flow through capacities; the min-cut theorem turns a bottleneck argument into a computable bound.
1 reviewed resources
Graph Laplacian
For a simple undirected graph, degree matrix minus adjacency matrix encodes connectivity and diffusion.
Video explanations to be added

Curriculum scope reference