← Home · Graph theory, four ways
Graph theory basics
Same idea, four ways to study it. Tap a style and find the one that clicks for you. 📺 Prefer to watch? Videos are on the lesson page.
🕸️ Just 4 words unlock this whole topic: vertex (a dot), edge (a line), degree (how many edges touch a dot), weight (a number on an edge). Learn those four and the rest is counting.

What it is

A graph is just dots joined by lines. The dots are vertices, the lines are edges. That is the whole idea. Graphs model anything where things connect to other things: roads between towns, friends in a group, tasks in a project.

The 4 words you actually need

Vertex (dot)
A point. Plural: vertices.
Edge (line)
A line joining two vertices.
Degree
How many edges touch a vertex.
Weight
A number on an edge (distance, cost, time).

The two rules to remember

Sum of all degrees = 2 × (number of edges)

Every edge has two ends, so it adds 2 to the total degree. This is the handshaking lemma, and it is your built-in check: count degrees, halve the total, you get the number of edges.

A tree with n vertices has exactly n − 1 edges

A tree is a connected graph with no cycles (no loops back to where you started). Connect 6 towns with the fewest possible roads and you always use 5.

Worked example

A graph has vertices P, Q, R, S, T with edges PQ, PR, QR, QS, RS, ST. Find each degree and verify the handshaking lemma.

  1. Count edges at each: P touches Q, R → 2. Q touches P, R, S → 3. R touches P, Q, S → 3. S touches Q, R, T → 3. T touches S → 1.
  2. Sum of degrees = 2 + 3 + 3 + 3 + 1 = 12
  3. Check: there are 6 edges, and 2 × 6 = 12 ✓

Watch out

• Degree counts edges, not other vertices, a loop (edge to itself) counts as 2.
• The number of odd-degree vertices decides if you can trace the graph in one go (that's Euler paths, next).
• A tree has no cycles, the moment there's a loop back, it's not a tree.
• Use the handshaking lemma to check your degree count: it must come to an even number.

A graph, labelled

A B C D deg 3 deg 2 deg 3 deg 2

4 vertices, 5 edges. Degrees: A=3, B=2, C=3, D=2. Sum = 10 = 2 × 5 edges. ✓ The diagonal A to C is what gives A and C their extra degree.

Why the handshaking lemma works

each edge = 2 handshakes

Picture each edge as two hands meeting. One edge, two hands. So if you count every "hand" (every degree) you've counted each edge twice. That's why the sum of degrees is always double the number of edges.

Tree: the skeleton with no loops

6 dots, joined with the fewest lines that keep them all connected = 5 edges, and not one cycle. That's a tree: n vertices, n − 1 edges.

Warm up first

Don't read yet, just have a go in your head:

What's the "degree" of a vertex?
The number of edges touching it. Just count the lines coming out of the dot.
A graph has 7 edges. What's the sum of all the degrees?
2 × 7 = 14. Every edge adds 2 to the total.
A tree connects 10 towns. How many roads?
n − 1 = 10 − 1 = 9 roads.

Faded example: degrees of P, Q, R, S, T

Rung 1 · watch one done fully

Edges PQ, PR, QR, QS, RS, ST. Degrees: P=2, Q=3, R=3, S=3, T=1. Sum = 12. Check: 6 edges × 2 = 12 ✓.

Rung 2 · you fill the gaps

Same edges. Degrees: P=?, Q=3, R=3, S=3, T=?. Sum = ?

Check my gaps
P = 2, T = 1, sum = 12.
Rung 3 · all you

A graph has edges AB, AC, AD, BC. Find every degree, then use the handshaking lemma to check. How many edges? Check below.

Check my answer
A touches B, C, D → 3. B touches A, C → 2. C touches A, B → 2. D touches A → 1. Sum = 3+2+2+1 = 8. Edges = 8 ÷ 2 = 4 ✓ (AB, AC, AD, BC).

Exam-style stretch: is it a tree?

A connected graph has 8 vertices and 9 edges. Could it be a tree? Explain.

Show the answer
No. A tree with 8 vertices must have exactly n − 1 = 7 edges. This one has 9, which is 2 more than 7, so it must contain cycles. More edges than n − 1 always means at least one loop.

Say it back

In one sentence, out loud: what does the handshaking lemma let you check? If you can say it, you've got it.

⚡ Graph theory, one look

Vertex / edgea dot / a line joining two dots
Degreenumber of edges touching a vertex (a loop counts as 2)
Weighta number on an edge (distance, cost, time)
Handshakingsum of all degrees = 2 × number of edges
Treeconnected, no cycles → n vertices, n − 1 edges
Connectedevery vertex reachable from every other
Odd degreeshow many odd-degree vertices decides traversability (Euler, next)
Trapdegree counts edges not vertices · sum of degrees is always even