Graph Terminology & Representations

Vertices, edges, degree, the handshaking theorem, and adjacency matrices.

The idea

A graph records which pairs of objects are related — which towns a road joins, which people know each other — and nothing else. Formally, a graph $G = (V, E)$ is a set $V$ of vertices together with a set $E$ of edges, each edge joining a pair of vertices. Where the vertices sit on the page is not part of the graph; two drawings that look nothing alike can show the same graph.

The degree of a vertex $v$, written $\deg(v)$, is the number of edges meeting $v$.

Theorem (Handshaking theorem).

In every graph $G = (V, E)$, the degrees of the vertices sum to twice the number of edges: $\sum_{v \in V} \deg(v) = 2|E|.$

In particular the degree sum of a graph is always an even number.

Besides being drawn, a graph can be stored as its adjacency matrix: number the vertices $v_1, \ldots, v_n$ and record, in row $i$ and column $j$, whether $v_i$ and $v_j$ are joined. Drawing and matrix carry exactly the same information, and we can put any question about the graph to either one.

Ways to work on it

• Walkthrough. Read degrees off a graph and discover the handshaking theorem.
• Practice. Recover the edge count from a list of degrees.
• Hardest. Read an adjacency matrix to find the edges and a degree.

Not sure where to start? Take the ten-question placement test.