Graphs
A graph is a set of points, the vertices, with some of them joined by lines, the edges. Almost all of graph theory is built on the few definitions here: what a graph is, loops and multiple edges, simple graphs, and the degree of a vertex. Then the first theorem, the Handshake Theorem, which says the degrees always add up to twice the number of edges, and what follows from it: every graph has an even number of vertices of odd degree, and many lists of numbers cannot be the degrees of any graph. The pigeonhole argument that two vertices of a simple graph share a degree is in pigeonhole-principle. First met in 2026-10-22-pigeonhole-principle-introduction-to-graph-theory. What comes after builds on these: getting around a graph (walks-trails-and-circuits), using every edge exactly once (euler-circuits-and-trails), writing a graph as a matrix (adjacency-matrices, incidence-matrices), and the connected graphs with no circuits (trees).
What a graph is
A graph \(G\) is a non-empty set of vertices \(V(G)\) and a (possibly empty) set of edges \(E(G)\), where each edge is associated with a set consisting of either one or two vertices.
The vertices an edge is associated with are its endpoints. An edge with two endpoints joins them, and an edge with one endpoint joins that vertex to itself.
- A graph must have at least one vertex, but it may have no edges at all.
- An edge is an object in its own right, not just a pair of vertices. Two different edges can have the same endpoints, and that is why edges are given their own names, \(e_1, e_2, \dots\).
Two standard words: two vertices joined by an edge are adjacent, and an edge is incident with each of its endpoints. A vertex with no edges at all is isolated.
Drawing a graph. Each vertex is a dot and each edge a line between the dots of its endpoints, or a small loop from a dot back to itself. The graph is only the vertices, the edges and which edges have which endpoints. Where the dots go, and whether the lines are straight or curved, carry no information, so the same graph can be drawn in many ways. Two lines that cross in a drawing do not meet at a vertex; only dots are vertices.
Figure 1: A graph with vertices \(v_1\) to \(v_5\) and edges \(e_1\) to \(e_6\). The edges \(e_1\) and \(e_2\) have the same endpoints, \(v_1\) and \(v_2\), so they are multiple edges. The edge \(e_4\) has the single endpoint \(v_3\), so it is a loop. \(v_5\) is an isolated vertex: no edge has it as an endpoint, but it is still part of the graph. The edge \(e_6\) joins \(v_2\) and \(v_4\), so those two vertices are adjacent and \(e_6\) is incident with each of them; \(v_1\) and \(v_3\) are not adjacent, since no edge joins them. The graph is not simple, because of the loop and because of the multiple edges.
| Edge | Endpoints |
|---|---|
| \(e_1\) | \(\{v_1, v_2\}\) |
| \(e_2\) | \(\{v_1, v_2\}\) |
| \(e_3\) | \(\{v_2, v_3\}\) |
| \(e_4\) | \(\{v_3\}\) |
| \(e_5\) | \(\{v_3, v_4\}\) |
| \(e_6\) | \(\{v_2, v_4\}\) |
The table is the graph. The drawing is one picture of it.
Loops and multiple edges
- A loop is an edge with only one endpoint. It joins a vertex to itself. Above, \(e_4\) is a loop at \(v_3\).
- Multiple edges (also called parallel edges) are two or more edges with the same set of endpoints. Above, \(e_1\) and \(e_2\) both join \(v_1\) and \(v_2\).
Both come up naturally when a graph models something. In the bridges of Königsberg, two land masses are joined by two bridges, which gives multiple edges (2026-07-27-welcome-and-intro-problems).
Simple graphs
A graph is simple if it has no loops and no multiple edges.
In a simple graph every edge has two different endpoints, and two vertices are joined by at most one edge. So an edge can be named by its endpoints, and a simple graph is just a set of vertices with some pairs of them joined.
A simple graph with \(n\) vertices has every degree at most \(n - 1\). A vertex can be joined to each of the other \(n - 1\) vertices at most once, and not to itself. This bound is one of the two quick tests for degree sequences.
Degree
The degree of a vertex \(v\), written \(\deg(v)\), is the number of edge ends incident with it.
Count the ends of edges at the vertex, not the edges.
- An ordinary edge has one end at each of its two endpoints, so it adds 1 to the degree of each.
- A loop has both of its ends at the same vertex, so it adds 2 to the degree of that vertex.
- An isolated vertex has degree 0.
In the graph above:
| Vertex | Edge ends at it | Degree |
|---|---|---|
| \(v_1\) | \(e_1\), \(e_2\) | 2 |
| \(v_2\) | \(e_1\), \(e_2\), \(e_3\), \(e_6\) | 4 |
| \(v_3\) | \(e_3\), \(e_4\) twice, \(e_5\) | 4 |
| \(v_4\) | \(e_5\), \(e_6\) | 2 |
| \(v_5\) | none | 0 |
The degrees add to \(2 + 4 + 4 + 2 + 0 = 12\), and there are 6 edges.
Why a loop counts 2: degree counts the ways out of a vertex along an edge. A loop can be set off along in either direction, so it gives two ways out. Counting it as 2 is also what makes the Handshake Theorem hold for every graph.
The Handshake Theorem
The Handshake Theorem. The sum of the degrees of a graph is twice the number of edges. If \(G\) is a graph with \(V(G) = \{v_1, v_2, \dots, v_n\}\) and \(|E(G)| = e\), then \[\sum_{i=1}^{n} \deg(v_i) = \deg(v_1) + \deg(v_2) + \cdots + \deg(v_n) = 2e.\]
Proof. Count the edge ends in the graph two ways. Every edge has exactly two ends: an edge with two endpoints has one at each, and a loop has both at its one endpoint. So there are \(2e\) ends in all. Every end is at exactly one vertex, and \(\deg(v_i)\) is the number of ends at \(v_i\). So adding the degrees over all the vertices counts each end exactly once, and the sum is \(2e\). \(\square\)
The name comes from people shaking hands at a party. Each handshake involves two hands, so the total number of hands shaken, added up person by person, is twice the number of handshakes.
Figure 2: The proof of the Handshake Theorem, on the graph above. Every edge is drawn in its own colour, with a dot of that colour at each of its two ends. The loop \(e_4\) has both of its dots at \(v_3\). The degree of a vertex is the number of dots at it, so adding up the degrees counts every dot once. Each edge has exactly two dots, so the 6 edges give 12 dots, and the degrees add to 12.
Using it. The theorem links the degrees to the number of edges, so either can be found from the other.
- Number of edges from the degrees. A graph with degrees \(4, 4, 3, 3, 2, 2\) has \(\frac{18}{2} = 9\) edges.
- No graph with an odd degree sum. There is no graph with 7 vertices each of degree 3: the degrees would add to 21, and 21 is not \(2e\) for any whole number \(e\). More generally, if every vertex has degree 3 then \(3n = 2e\), so the number of vertices \(n\) must be even.
- Edges of a complete graph, below.
Odd-degree vertices come in pairs
Corollary. Every graph has an even number of vertices of odd degree.
Proof. Split the sum of the degrees into the vertices of even degree and the vertices of odd degree:
\[\underbrace{\sum_{\deg(v) \text{ even}} \deg(v)}_{\text{even}} \;+\; \sum_{\deg(v) \text{ odd}} \deg(v) \;=\; 2e.\]
The first sum is a sum of even numbers, so it is even. The right side is even. So the second sum, being the difference of two even numbers, is even. It is a sum of odd numbers, and a sum of odd numbers is even exactly when there is an even number of terms: odd numbers pair up into even sums, and one left over makes the total odd. So the number of vertices of odd degree is even. \(\square\)
Figure 3: The corollary on a graph with degrees 3, 3, 2, 1, 1, odd degrees in red and even in blue. The degree sum is \(2e = 10\), even. Its even part, 2, is even, so its odd part, \(3 + 3 + 1 + 1\), must be even as well. A sum of odd numbers is even only when the odd numbers pair off, each pair adding to an even number. Here the four odd degrees make two pairs. A fifth vertex of odd degree would be left without a partner and make the total odd, which no graph allows.
The corollary says nothing about the vertices of even degree. Their number can be odd or even: one vertex joined to four others has one vertex of even degree, and a path of four vertices has two. That is worked as a multiple-choice question in 2026-10-22-pigeonhole-principle-introduction-to-graph-theory.
In practice the corollary is the quickest check on a list of degrees: count the odd entries. If there is an odd number of them, no graph has those degrees.
Degree sequences
The list of the degrees of the vertices in a graph is called the degree sequence of the graph.
It is usually written largest first. The graph above has degree sequence \(4, 4, 2, 2, 0\). Only the list of numbers matters, not which vertex has which.
The usual question runs the other way: given a list, is there a graph, often a simple graph, with exactly those degrees? Two checks rule a list out:
- The sum must be even, by the Handshake Theorem. Equivalently, the number of odd entries must be even. This holds for every graph.
- For a simple graph with \(n\) vertices, no entry can be more than \(n - 1\). A list of \(n\) numbers with an entry of \(n\) or more has no simple graph.
These checks are necessary, not sufficient. A list can pass both and still have no simple graph. Take \(3, 3, 3, 1\). The sum is 10, which is even, and no entry is more than \(n - 1 = 3\). But with 4 vertices, a vertex of degree 3 in a simple graph is joined to all three others. There are three such vertices, and each of them is joined to the fourth vertex, which therefore has degree 3, not 1. So no simple graph has degree sequence \(3, 3, 3, 1\).
Figure 4: Why no simple graph has degree sequence 3, 3, 3, 1. In a simple graph on 4 vertices, a vertex of degree 3 is joined to every other vertex. The three vertices that need degree 3, black, must each be joined to the fourth vertex, red, which is then forced to have degree 3 as well. The list passes both quick checks, an even sum and no degree above 3, and still has no simple graph.
So, after the two checks, a list that passes either gets a drawing or an argument like this one. Small cases can be settled by hand, building the graph from the vertex of largest degree down. A complete test for when a list is the degree sequence of a simple graph does exist (the Havel–Hakimi and Erdős–Gallai theorems), but it is beyond this course.
Without the word “simple”, the answer is easy. If loops are allowed, every list with an even sum is the degree sequence of some graph. The odd entries come in an even number, so pair them up and join each pair by an edge. Now every vertex still needs an even number of edge ends, and a loop supplies 2, so add loops until each vertex has its degree. For example, \(3, 2, 1\) has no simple graph, since degree 3 is impossible with only 3 vertices, but a graph with multiple edges has those degrees (2026-10-22-pigeonhole-principle-introduction-to-graph-theory).
Worked: which lists are degree sequences
For each list, is there a simple graph with those degrees?
| List | Sum | Largest vs \(n - 1\) | Simple graph? |
|---|---|---|---|
| \(2, 2, 2, 2\) | 8 | \(2 \le 3\) | yes: a square |
| \(3, 2, 1\) | 6 | \(3 > 2\) | no: too large |
| \(4, 3, 2, 2, 2, 2, 1, 1\) | 17 | \(4 \le 7\) | no: odd sum (three odd entries) |
| \(1, 1, 1, 1\) | 4 | \(1 \le 3\) | yes: two edges with no common vertex |
| \(5, 5, 5, 5, 5, 5\) | 30 | \(5 \le 5\) | yes: the complete graph \(K_6\) |
| \(3, 3, 3, 1\) | 10 | \(3 \le 3\) | no: passes both checks, fails as shown |
| \(4, 4, 3, 3, 2, 2\) | 18 | \(4 \le 5\) | yes: 9 edges |
The first five are drawn in 2026-10-22-pigeonhole-principle-introduction-to-graph-theory. For the last, name the vertices \(a, b, c, d, e, f\) with the degrees in that order, and take the edges \(ac, ad, ae, af, bc, bd, be, bf, cd\). Then \(a\) and \(b\) are each joined to \(c, d, e, f\); \(c\) and \(d\) to \(a\), \(b\) and each other; and \(e\) and \(f\) to \(a\) and \(b\).
Complete graphs
The complete graph \(K_n\) is the simple graph with \(n\) vertices in which every pair of different vertices is joined by an edge. It is the standard name for this graph. Every vertex is joined to the other \(n - 1\), so every degree is \(n - 1\), the most a simple graph allows. \(K_6\) is the graph with degree sequence \(5, 5, 5, 5, 5, 5\).
How many edges? By the Handshake Theorem,
\[n(n - 1) = 2e, \qquad\text{so}\qquad e = \frac{n(n-1)}{2}.\]
Or count directly: an edge of \(K_n\) is a choice of 2 of the \(n\) vertices, so there are \(\binom{n}{2} = \frac{n(n-1)}{2}\) edges (counting-selections). The two counts agree. \(K_6\) has \(\frac{6 \cdot 5}{2} = 15\) edges.
\(\binom{n}{2}\) is the most edges a simple graph on \(n\) vertices can have. Each edge of a simple graph is a different pair of vertices, and there are only \(\binom{n}{2}\) pairs. \(K_n\) uses every pair, so it is the only simple graph on \(n\) vertices that reaches the bound.
Figure 5: The complete graphs \(K_1\) to \(K_5\), each with every pair of vertices joined. Each vertex of \(K_n\) has degree \(n - 1\), so the degrees add to \(n(n-1)\) and there are \(\frac{n(n-1)}{2}\) edges: 0, 1, 3, 6 and 10. In \(K_4\) and \(K_5\) some lines cross where there is no vertex. Only the dots are vertices.
Common mistakes
- Counting a loop once. A loop adds 2 to the degree of its vertex. Counting it as 1 makes the degree sum odd and breaks the Handshake Theorem.
- Treating a crossing as a vertex. Lines that cross in a drawing are not joined. A vertex is a dot.
- Taking an even sum as enough. The Handshake Theorem rules a list out when its sum is odd, but an even sum does not make a simple graph exist: \(3, 2, 1\) and \(3, 3, 3, 1\) both have even sums and no simple graph.
- Forgetting the word “simple”. Without it, loops and multiple edges are allowed, and any list with an even sum has a graph. With it, every degree is at most \(n - 1\).
- Mixing up the corollary. The number of vertices of odd degree is always even. The number of vertices of even degree can be anything.
- Reading the drawing as the graph. Where the dots are and how the lines bend do not matter. The graph is the vertices, the edges and their endpoints.
See also
- pigeonhole-principle — every simple graph with at least two vertices has two vertices of equal degree
- counting-selections — \(\binom{n}{2}\), the number of edges of \(K_n\)
- 2026-07-27-welcome-and-intro-problems — the bridges of Königsberg as a graph
- walks-trails-and-circuits — walks, trails, circuits and connected graphs
- euler-circuits-and-trails — when a graph can be traced using every edge exactly once
- adjacency-matrices · incidence-matrices — a graph written as a matrix
- trees — connected graphs with no circuits
- 2026-10-22-pigeonhole-principle-introduction-to-graph-theory — Lecture 33
- 2026-10-26-walks-trails-and-circuits — Lecture 34, which recaps these definitions
- practice-problems — §43, with full worked solutions