Graphs, vertices and edges
A network is points with some pairs linked. What can be said about it before anyone asks for a route through it?
Where you are 4 inside
What this area is about
A graph is a finite nonempty set of vertices together with edges, each edge joining two different vertices. That bare picture models cables, friendships and flights alike. This area sets up the vocabulary and first facts: how many edges meet at a vertex, what numbers or directions an edge can carry, how a graph is stored as a table, and when two drawings show the same graph.
How these fit together
Definitions and a first result. Degree, the handshake lemma and complete graphs defines simple graphs and degree, and proves that in every graph the degrees sum to 2|E|.
Extra structure. Weighted and directed graphs put a number on every edge, or an arrow on it, so that a route has a weight and degree splits into in and out.
Comparing and computing. Graph isomorphism makes “the same graph” precise as a bijection of vertices that keeps every edge, and uses invariants such as degrees to prove two graphs differ. Adjacency matrices and their powers store a graph as a 0 and 1 matrix A; the entry in row i, column j of A^k counts the walks of length k from v_i to v_j.
A path through it
Degree first: the other three lessons borrow its definitions, and isomorphism needs it. Then take walks, paths and cycles: weighted graphs price its walks, and graph isomorphism and adjacency matrices both require it. Finish with those three, weighted graphs first.
After this come Euler circuits, bipartite graphs and, from weighted graphs, shortest paths and minimum spanning trees.