HelpContactFor teachers and institutes
>_StemPy Lab
Mock TestsClasses

>_StemPy Lab

Learn. Solve. Code the solutions. Test yourself.

Live examsFree mock exams, timed and rankedEveryone starts together, and your score and rank come the moment it ends.See the exams →
Live examsInternational live exams are comingTell us which exam you want first. Timed practice papers are open now.See what is coming →

Learn

  • Physics
  • Chemistry
  • Mathematics
  • Biology
  • Python Programming
  • Statistics & Data Science
  • Computer Science
  • Space Science and Astronomy
  • Earth and Environmental Science
  • Classes
  • Groups

Practice

  • Problems
  • Quizzes
  • Mock Tests
  • Prepare for an Exam
  • Question Sets
  • Exams
  • Certificates
  • Python Labs
  • AI Practice Generator
  • Student-Created Tests

Community

  • Discussions
  • Resources
  • Notes
  • Glossary
  • Blog

Account

  • Log in
© 2026 senLearn. All rights reserved.HelpFor SchoolsAboutContactPrivacy PolicyTerms of UseRefund Policy
Graph Theory
  1. 1Graphs, degrees and the handshake lemma
  2. 2Trees, bipartite graphs and Euler trails
  3. 3Planar graphs, colouring and Ramsey numbers
  1. Mathematics
  2. /Graph Theory
  3. /Graphs, degrees and the handshake lemma

Course 30.3·Lesson 1 of 3

Graphs, degrees and the handshake lemma

A graph is a set of vertices with some pairs joined by edges. The degree of a vertex is the number of edges at it. Every edge has two ends, so the degrees add up to twice the number of edges: the handshake lemma. So the number of odd vertices is always even. Paths, cycles and connected components describe how a graph hangs together.

about 25 min1 simulation1 practice question1 Python program5 questions to check yourself

This lesson is free to read. Enroll free to keep your place and take the tests.

Lesson 1 of 3Show all lessonsHide
Graph Theory
  1. 1Graphs, degrees and the handshake lemma
  2. 2Trees, bipartite graphs and Euler trails
  3. 3Planar graphs, colouring and Ramsey numbers

Try the code and the simulations beside the lesson.

What you will be able to do

  • describe a graph by its vertices, edges and degrees;
  • use the handshake lemma and its corollary about odd vertices;
  • recognise paths, cycles, connected graphs and components, and test a list of degrees.

Dots and lines

Five friends message each other. Draw a dot for each friend and a line between two friends who have exchanged messages. The picture is a graph. The dots are vertices and the lines are edges. Only who is joined to whom matters, not where the dots sit or how the lines bend.

In this chapter a graph is simple: no edge joins a vertex to itself (a loop), and two vertices are joined by at most one edge. A graph that allows several edges between two vertices is called a multigraph. Euler's bridges in the next lesson need one.

The degree of a vertex, written deg⁡v\deg vdegv, is the number of edges at it. A vertex of degree 000 is isolated. A graph in which every vertex has the same degree kkk is called kkk-regular.

A graph with six vertices labelled with their degrees. Vertex A is joined to B, C and D, so it shows 3. B is joined to A and C (degree 2), C to A, B and D (degree 3), D to A, C and E (degree 3), E to D (degree 1), and F stands alone with degree 0. A note says the degrees add up to 12, twice the 6 edges.

The handshake lemma

At a party some guests shake hands. Add up the numbers of handshakes of all the guests. What do you get?

Every handshake involves two people, so it is counted twice. The same holds in any graph.

Handshake lemma. In every graph, ∑vdeg⁡v=2E\displaystyle\sum_{v} \deg v = 2Ev∑​degv=2E, where EEE is the number of edges.

Corollary. The number of vertices of odd degree is even.

Proof. Split the sum of degrees into the even degrees and the odd degrees. The total 2E2E2E is even, and so is the sum of the even degrees. So the sum of the odd degrees is even, and a sum of odd numbers is even only when there is an even number of them.

So 777 people cannot each shake hands with exactly 333 others: the degree sum would be 212121, which is odd.

Complete graphs and degree lists

The complete graph KnK_nKn​ joins every two of its nnn vertices. Each vertex has degree n−1n - 1n−1, so

E=n(n−1)2=(n2).\displaystyle E = \dfrac{n(n - 1)}{2} = \dbinom{n}{2}.E=2n(n−1)​=(2n​).

The list of degrees, largest first, is the degree sequence. An even sum is needed, but it is not enough. The list 3,3,1,13, 3, 1, 13,3,1,1 has an even sum, yet no simple graph has it. The two vertices of degree 333 would each be joined to all three others, so the last two vertices would have degree at least 222.

Havel–Hakimi test. Remove the largest degree ddd, and subtract 111 from each of the next ddd degrees. The old list is a degree sequence exactly when the new list is one. Repeat until the answer is clear.

For 3,3,1,13, 3, 1, 13,3,1,1: remove 333 and subtract from the next three. This gives 2,0,02, 0, 02,0,0. A vertex of degree 222 needs two other vertices to join, and here no other vertex can take an edge. So 3,3,1,13, 3, 1, 13,3,1,1 fails.

Walks, paths and cycles

  • A walk is a sequence of vertices in which each one is joined to the next.
  • A path is a walk with no repeated vertex.
  • A cycle is a closed walk with at least 333 vertices and no repeat except the start at the end. CnC_nCn​ is the cycle on nnn vertices.

A graph is connected when there is a path between every two vertices. Otherwise it falls into separate pieces called components.

Two classic facts

  1. Two equal degrees. In a simple graph with n≥2n \ge 2n≥2 vertices, two vertices have the same degree. The degrees lie in 0,1,…,n−10, 1, \dots, n - 10,1,…,n−1. But 000 and n−1n - 1n−1 cannot both occur, because a vertex of degree n−1n - 1n−1 is joined to every other vertex. So nnn degrees take at most n−1n - 1n−1 values, and the pigeonhole principle finishes the proof.
  2. Many edges force connection. A simple graph on nnn vertices with more than (n−12)\dbinom{n - 1}{2}(2n−1​) edges is connected. If it were not, its vertices would split into two groups with no edge between them. The most edges such a graph can have is (n−12)\dbinom{n - 1}{2}(2n−1​), from Kn−1K_{n-1}Kn−1​ and one isolated vertex.

Practise with new numbers

Try it in Python

The program stores a graph as a list of edges. It works out the degrees, checks the handshake lemma, and finds the component of a vertex by searching outwards from it.

Read it first. Then run it. Is the graph connected?

1. Remove the edge (3, 4) from the list. Which components do you get now?

2. Add the edge (0, 5). Predict the new sum of the degrees first.

Common mistakes

  • Counting each edge once. The degree sum counts every edge twice.
  • Trusting an even sum. An even sum does not make a list a degree sequence. Use the Havel–Hakimi test.
  • Mixing up path and walk. A path never repeats a vertex.
  • Drawing matters? Two drawings with the same vertices and edges are the same graph, however the lines cross.

Remember these

  • ∑deg⁡v=2E\displaystyle\sum \deg v = 2E∑degv=2E, so the number of odd vertices is even.
  • KnK_nKn​ has (n2)\dbinom{n}{2}(2n​) edges and every vertex has degree n−1n - 1n−1.
  • Every simple graph with at least two vertices has two vertices of equal degree.
  • More than (n−12)\dbinom{n - 1}{2}(2n−1​) edges on nnn vertices force a connected graph.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

  1. A graph has degrees 4, 3, 3, 2, 2, 2. How many edges does it have?
  1. Can a graph have exactly 555 vertices of odd degree?
  1. How many edges does K8K_8K8​ have?
  1. Is 2,2,2,1,12, 2, 2, 1, 12,2,2,1,1 the degree sequence of a simple graph?
  1. A simple graph on 666 vertices has 111111 edges. Must it be connected?

References

  • D. B. West, Introduction to Graph Theory, Chapter 1.
  • R. J. Wilson, Introduction to Graph Theory, Chapters 1 and 2.

Enroll free in Graph Theory

Every lesson is open to read. Enrolling also lets you:

  • Mark lessons done and carry on where you stopped.
  • Take the tests of this lesson and its course.
  • Count the course towards the certificate for its chapter.
No payment. You can leave at any time.

Problems (3)

At a meeting each delegate shakes hands with some of the others, never twice with the same person…Hard · High School (11–12) · by StemPy Lab
A simple graph has exactly 12 edges. Three of its vertices have degree 4, and every other vertex…Hard · High School (11–12) · by StemPy Lab
A computer network has 10 machines, and some pairs are joined by cables, at most one cable per pair…Advanced · High School (11–12) · by StemPy Lab
Next: lesson 2Trees, bipartite graphs and Euler trails
← Graph Theory
← PreviousTrees, bipartite graphs and Euler trails →

Discussion (0)

Log in to join the discussion.

Loading…

Python Labs (1)

Degrees and componentsPython Lab · by StemPy Lab