Introductory graph theory
Bridges, cables, schedules and maps all reduce to dots and lines. Which questions about them can be settled by a count or a method instead of trying every possibility?
Where you are 10 inside
What this area is about
A graph is a set of vertices with edges joining some pairs. Forgetting everything else about a network, its shape and its scale, often makes a hard question exact: can a route use every link once, how many links must a connected network have, how few colors keep neighbors apart. The graphs here are finite and, unless a lesson says otherwise, simple.
How these fit together
Foundations. Graphs, vertices and edges gives degree, weighted and directed graphs, isomorphism and adjacency matrices. Walks, paths, cycles and connected graphs defines routes and components.
Routes. Euler circuits: a connected graph with at least one edge has a closed route using every edge once exactly when every degree is even. Hamiltonian paths and cycles visit every vertex once, and no simple test for them is known.
Trees and algorithms. Trees: a tree on n vertices has n - 1 edges. Shortest paths (Dijkstra’s algorithm, weights \ge 0) and minimum spanning trees are procedures on weighted graphs.
Drawing and coloring. Euler’s formula: a connected plane drawing has V - E + F = 2. Graph coloring and bipartite graphs, the graphs with a proper 2-coloring, follow.
A path through it
Start with degree, then walks, paths and cycles, then weighted graphs, isomorphism and adjacency matrices. After walks come Euler circuits, Hamiltonian cycles, shortest paths and trees (which also need induction); minimum spanning trees need weighted graphs. Euler’s formula comes before coloring, and coloring before bipartite graphs.