Back to the on-screen lesson ·
Vertices, edges and degrees; the count of one set two ways that gives the handshake lemma; and the parity check that rules a graph out without drawing anything.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to read a graph as a set of vertices with a set of edges, find degrees, and use the handshake lemma — that the degrees add to twice the edge count — to find an edge count or to rule a described graph out entirely. You will also be able to say why the number of odd-degree vertices is always even, count the edges of a complete graph two different ways, and say why an even degree total does not on its own guarantee that a graph exists.
A graph is a set together with a set of pairs from it, which is exactly the relation of lesson 13 drawn as a picture. And the counting of unit 4 is what answers most questions about one: the edges of a complete graph are the committees of two of lesson 17, with nothing changed but the vocabulary.
A graph has a set of vertices and a set of edges, each edge joining two distinct vertices; no edge is repeated and none joins a vertex to itself, unless the course says otherwise. The degree of a vertex is the number of edges meeting it. A walk is a sequence of edges laid end to end; a path repeats no vertex; a cycle is a closed path. A graph is connected when some walk joins every pair of vertices.
The handshake lemma. In any graph, the sum of the degrees equals twice the number of edges.
$$\sum_{v} \deg(v) = 2|E|$$
The proof is a count of one set two ways, which is unit 4's technique arriving in a new subject. Count the pairs (a vertex, an edge meeting it). Sorting by vertex gives $\sum_v \deg(v)$; sorting by edge gives $2|E|$, since every edge has exactly two ends. Same set, two counts.
Two consequences are used constantly.
The degrees add to an even number, so a list of degrees with an odd total is the degree sequence of no graph at all. That is an impossibility proof costing one addition.
The number of odd-degree vertices is even. Split the sum into the even degrees and the odd ones; the even part is even and the total is even, so the odd part is even — and a sum of odd numbers is even only when there are an even number of them.
The complete graph $K_n$ joins every pair, so it has $\binom{n}{2} = n(n-1)/2$ edges and every vertex has degree $n-1$. Both counts agree, as they must: $n(n-1)$ halved.
That is nearly all the machinery unit 5 needs. What follows — trees, Euler circuits, planarity — is this lemma plus one new idea each time.
Another way: steps
To answer a question about degrees:
Another way: picture
A graph with each edge drawn as a piece of string, and a tally kept at every vertex of how many string-ends are tied there. Every piece of string contributes exactly two ends, wherever they are, so the tally total is twice the number of pieces — however tangled the picture is.
A graph on a set $V$ is a symmetric, irreflexive relation on $V$: $u$ is related to $v$ exactly when there is an edge between them. Everything lesson 13 said applies, and the picture is a way of seeing it rather than a different object.
That is worth saying because it settles what a graph is not. It is not a drawing. Two pictures that look nothing alike are the same graph if the same pairs are joined, and a theorem about a graph may never appeal to where the vertices were placed. Planarity in lesson 23 is the one place where drawings genuinely matter, and even there the theorem is about whether some drawing exists, not about a particular one.
The practical consequence: when a problem gives you a picture, extract the degrees and the adjacencies first, and then argue from those.
Forgetting the factor of two. The degrees add to $2|E|$, not $|E|$. A graph with degree total $12$ has six edges.
Reading an even total as a guarantee. An even total is necessary for a degree sequence to be realisable and is not sufficient: $4, 4, 4, 4$ on four vertices adds to sixteen and is impossible, because no vertex can have degree four when there are only three others.
Counting a vertex's own edges twice. In a simple graph each edge meets a vertex once.
Arguing from the drawing. Crossings in a picture are an artefact of the drawing and are not part of the graph.
It is tempting to file $\sum \deg(v) = 2|E|$ with the other formulas and use it by substitution. Its content is the argument: one set of vertex-edge incidences, counted by vertex and counted by edge. Seeing it that way is what lets you adapt it — to directed graphs, where in-degrees and out-degrees each add to $|E|$, or to multigraphs, where an edge from a vertex to itself contributes two to its degree. The formula changes; the argument does not.
Can seven people each shake hands with exactly three others? Model it: seven vertices, every degree three.
Turn the situation into a graph first.
The degrees would add to $7 \times 3 = 21$, which is odd.
One multiplication.
But a degree total is twice the edge count and so is even. So no such arrangement exists — and the proof never attempted a single arrangement.
An impossibility proof with no cases in it.
How many edges has the complete graph on six vertices? As subsets: an edge is a pair, so $\binom{6}{2} = 15$.
Counting pairs.
By the lemma: every vertex meets the other five, so every degree is five and the total is $30$.
Counting degrees.
Halving gives $15$. The agreement is a check on both, and it is also the handshake lemma's proof in miniature — the same incidences, counted by edge and by vertex.
Two counts of one set.
Add the degrees: $5 \times 3 + 2 \times 4 = 15 + 8 = 23$.
Total first.
That is odd — and a degree total must be twice the edge count.
Check the parity before dividing.
So there is no such graph, and the question has no numerical answer. Notice the check it would have failed anyway: five vertices of odd degree is an odd number of odd-degree vertices, which the lemma also forbids. Two ways of seeing the same impossibility.
A graph has degree sequence $1, 2, 3, 4, 4$. Fill in the total degree and the number of edges.
| Number | |
|---|---|
| Sum of the degrees | |
| Number of edges |
A graph has $7$ vertices, each of degree $2$. How many edges does it have?
Answer:
In the complete graph on $5$ vertices every pair is joined by an edge. How many edges is that?
Answer:
Match each word to what it counts or names in a graph.
| How many edges meet that vertex | How many vertices there are | How many edges there are | Some walk joins every pair of vertices | |
|---|---|---|---|---|
| The degree of a vertex | ||||
| The order of the graph | ||||
| The size of the graph | ||||
| The graph is connected |
Mark every list below that could be the degree sequence of some graph.
This task has no paper form; do it on a device.
Could $6$ people meet so that each of them shakes hands with exactly $3$ of the others?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A graph has degree sequence $3, 3, 3, 1$. Fill in the total degree and the number of edges.
| Number | |
|---|---|
| Sum of the degrees | |
| Number of edges |
You can find degrees and edge counts and use parity to rule a graph out. Say in your own words the two-way count that proves the handshake lemma, and why the number of odd-degree vertices must be even. Next: the graphs with as few edges as connectivity allows.
10. Your turn: a graph has five vertices of degree $3$ and two of degree $4$. How many edges?, step 3