Glossary

Finds shortest paths from one vertex to all others even when some edge weights are negative, by relaxing every edge repeatedly.

In a graph where every edge counts the same, BFS from a vertex finds the shortest path to every other vertex for free.

Finding the largest possible pairing between two groups can be solved by turning it into a flow network and finding the maximum flow.

Two systematic ways to visit every vertex of a graph reachable from a start vertex: BFS fans out level by level, DFS plunges as deep as possible before backing up.

Except for complete graphs and odd cycles, every connected graph can be properly colored with no more colors than its largest degree.

The set of vertices whose eccentricity equals the graph's radius -- the most centrally located vertices.

chi(G) counts the fewest colors needed to properly color a graph; Delta is the largest degree any single vertex has.

The graph on the same vertices where every non-edge of the original becomes an edge, and every edge disappears.

A graph split into two groups of sizes r and s, with every vertex in one group joined to every vertex in the other and no edges within a group.

A graph on n vertices where every pair of distinct vertices is joined by an edge.

For any way of splitting a tree's vertices into two groups, there is exactly one tree edge crossing between them.

A graph on n vertices arranged in a single closed loop, each vertex adjacent to exactly two neighbors.

Finds the shortest route from one starting vertex to every other vertex in a graph with non-negative edge weights, always settling the closest unvisited vertex next.

Two sufficient (not necessary) degree conditions that guarantee a graph is Hamiltonian: Dirac's checks every vertex's own degree, Ore's checks the degree sum of every non-adjacent pair.

The length of the shortest path between two vertices, counted by number of edges.

A second graph built from a planar drawing's faces -- one vertex per face, one edge per crossing of an original edge -- that swaps the roles of vertices and faces.

How far a vertex sits from its farthest neighbor (eccentricity), and the biggest and smallest such distances across the whole graph (diameter, radius).

Several different properties -- connected and acyclic, exactly n-1 edges and connected, exactly one path between any two vertices -- that all pick out the same class of graphs: trees.

For any connected planar drawing, vertices minus edges plus faces always equals 2.

A connected graph has an Euler circuit exactly when every vertex has an even number of edges touching it.

A graph that has a closed walk using every edge exactly once.

A directed graph where each edge has a capacity limit, plus a source and a sink, used to model how much can move through the network at once.

Computes the shortest distance between every pair of vertices at once, by considering each vertex in turn as a possible shortcut.

Every flat map needs at most four colors so no two touching regions match, and (unlike the famously computer-verified four-color proof) the weaker five-color version has a proof anyone can check by hand.

A matrix built from a graph's degree and adjacency matrices whose eigenvalues reveal connectivity properties an adjacency matrix alone can miss.

Three different ways to store the same graph in a computer: a list of each vertex's neighbors, a matrix of who's adjacent to whom, or a matrix of which vertex touches which edge.

The list of eigenvalues of a graph's adjacency matrix, which turns out to encode a surprising amount of the graph's structure.

Coloring vertices one at a time in some order, always giving each vertex the lowest-numbered color none of its already-colored neighbors is using.

A graph that has a cycle visiting every vertex exactly once.

The graph of a k-dimensional cube: one vertex per length-k binary string, with an edge between any two strings differing in exactly one position.

Builds a minimum spanning tree by adding the cheapest edges first, skipping any that would create a cycle.

A graph is planar exactly when it doesn't secretly contain a stretched-out copy of the two smallest non-planar graphs, K5 and K3,3.

A graph can be properly 2-colored exactly when it has no odd-length cycle.

The most flow that can possibly get from source to sink always equals the capacity of the tightest bottleneck separating them.

The maximum number of vertex-disjoint routes between two points equals the fewest vertices needed to block every route between them.

Graph problems (like finding a Hamiltonian cycle) for which no efficient algorithm is known, and which are provably as hard as any problem whose answer can at least be checked quickly.

A graph on n vertices in a single line, each internal vertex adjacent to exactly two neighbors and the two ends adjacent to just one.

A graph that can be drawn on a flat page with no two edges crossing.

Builds a minimum spanning tree by growing a single connected piece outward, always adding the cheapest edge leaving it.

The smallest party size that guarantees either a group of mutual friends or a group of mutual strangers of a given size, no matter how the friendships are arranged.

The largest groups of vertices in a directed graph where every vertex can reach every other vertex in the same group by following directed edges.

Lining up the vertices of a directed acyclic graph so every edge points from an earlier vertex to a later one.

A data structure that tracks which items belong to the same group, and can quickly check whether two items are already in the same group or merge two groups together.

The fewest vertices (or edges) that have to be removed to disconnect a graph -- a numeric measure of how resilient it is.

The two building blocks of a graph G, written V(G) for its vertices and E(G) for its edges.

A cycle of n vertices plus one more vertex in the middle connected to all of them, like spokes on a wheel.