Graphs · step 1 of 14

Degrees & the handshake lemma

The degree of a vertex is the number of edge-ends meeting it, with a loop counting twice. The handshake lemma says the degrees sum to exactly 2|E|, because every edge contributes one to each of its two endpoints. Its immediate corollary — that the number of odd-degree vertices is even — settles a surprising number of existence questions in a single line.

Practise degrees & the handshake lemma free → All Graphs subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

Sum the degreesΣ deg(v) = 2|E| for every graph, directed or not, simple or with loops (loops count 2).
Solve for the unknownGiven any two of: number of edges, number of vertices, degree pattern — the lemma determines the third.
Use parity to refuteIf a proposed degree sequence has an odd sum, no graph realises it. This is the fastest impossibility argument available.
Count odd-degree verticesThey always come in pairs, since the even-degree vertices contribute an even amount to an even total.

Worked example

Does a graph exist with 5 vertices each of degree 3?

Sum of degrees would be 5 × 3 = 15.
The handshake lemma requires this to equal 2|E|, an even number.
15 is odd, so no such |E| exists.
Equivalently, there would be five odd-degree vertices, contradicting the even-count corollary.

Answer. No such graph exists — the degree sum is odd, which the handshake lemma forbids.

Where marks get dropped

These are the specific errors that cost credit on degrees & the handshake lemma questions — QED's rubric penalises each of them separately.

Counting a loop once. A loop adds 2 to its vertex’s degree, and forgetting this breaks the lemma.
Applying the lemma to directed graphs unmodified. There, Σ in-degrees = Σ out-degrees = |E|, not 2|E|.
Confusing the number of edges with the number of edge-ends. The lemma counts ends, which is why the factor 2 appears.

Practise this until it is automatic

Unlimited fresh questions

QED generates new degrees & the handshake lemma problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Graphs mastery is tracked so you know when this is exam-ready.

Degrees & the handshake lemma — frequently asked questions

Why is it called the handshake lemma?

If people shake hands at a party, the total number of hands shaken is twice the number of handshakes — the same double count as vertices and edges.

Does it hold for multigraphs?

Yes. Parallel edges each contribute to both endpoints, and loops contribute 2 to one vertex, so the identity is unaffected.

What is the maximum degree in a simple graph?

At most |V| − 1, since a vertex can join each other vertex at most once. A graph where every vertex achieves this is complete.

The rest of Graphs

Terminology, connectivity, trees, paths and cycles. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make degrees & the handshake lemma exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →