Lesson 1 of 8 · 16 min
Graphs, vertices, edges and degree
Read a graph as vertices joined by edges, find the degree of every vertex — counting a loop twice — and use the sum of the degrees to count edges.
What you will be able to do
- Identify the vertices, edges, loops and multiple edges of a graph.
- Find the degree of a vertex, counting a loop twice.
- Use the fact that the sum of the degrees is twice the number of edges.
- Recognise simple graphs and subgraphs.
Picture the road map you would use to drive from Cairns up to the Atherton Tableland. It is full of detail: bends, hills, distances, town names. Now suppose all you want to know is which towns are linked directly by a road. You could throw away almost everything and keep only a dot for each town and a line for each road.
That stripped-down picture is a graph.
Seven towns near Cairns and the main roads joining them. The positions are only roughly geographic — a graph records connections, not distances.
Definition
Graph, vertex and edge
A graph is a set of points, called vertices (or nodes), joined by lines called edges (or arcs). One point is a vertex; several are vertices.
Two drawings that join the same pairs of vertices are the same graph, however differently they are drawn.
The graph above has 7 vertices and 8 edges. Where an edge is drawn, how long it is, and whether it is straight or curved make no difference — only the two vertices it joins matter.
Edges may cross in a drawing without meeting. There is a vertex only where a dot is drawn, the way a road overpass crosses another road without an intersection.
Definition
Loops and multiple edges
A loop is an edge that starts and finishes at the same vertex. Multiple edges are two or more edges joining the same pair of vertices — for example, two different roads between the same two towns.
A loop at , and two edges joining and .
Definition
Degree of a vertex
The degree of a vertex, written , is the number of edges that meet it. A loop meets its vertex twice — at both of its ends — so it adds 2 to the degree.
A vertex of degree 0 is an isolated vertex. A vertex is called odd or even according to its degree.
In the graph above, meets one edge to , two edges to and one edge to , so . Each of the multiple edges counts separately.
In the graph with the loop, what is ?
Find the degree of each town. Which towns have odd degree? Then add all seven degrees and compare the total with the number of roads.
Cairns and Mareeba have degree 3, and the other five towns have degree 2. The total is , and the graph has 8 edges: . That is no coincidence.
Key idea
The sum of the degrees
In every graph,
Every edge has two ends, and each end adds 1 to the degree of the vertex it meets. (A loop has both ends at one vertex, which is why it adds 2 there.)
Why every graph has an even number of odd vertices
The sum of the degrees is , which is even. The even degrees add to an even number, so the odd degrees must add to an even number too. A sum of odd numbers is even only when there is an even number of them.
So every graph has 0, 2, 4, … vertices of odd degree — never 1 or 3. You will use this fact in the lesson on Eulerian graphs.
Worked example
Degrees in a graph with a loop and multiple edges
For the graph shown:
(a) find the degree of each vertex
(b) use the degrees to find the number of edges, then check by counting the edges.
Step 1: Count the edge-ends at P
Edges and meet , and so does the loop. The loop has both of its ends at , so it counts twice: .
The degree counts edge-ends. A loop starts and finishes at , so it brings two ends to .
Step 2: Count the edge-ends at Q, R and S
meets , the two edges to , and , so . meets the two edges to and , so . meets , and , so .
The two edges between Q and R are separate edges, so each one counts once at Q and once at R.
Step 3: Add the degrees
Step 4: Halve the total to get the number of edges
Every edge adds 2 to the total, one for each end, so there are edges.
Step 5: Check by counting
, (twice), , , and the loop at : 7 edges. ✓
Try it yourself first, then check the working one step at a time.
Answer
, , and . The graph has 7 edges.
Method
Count the edge-ends at each vertex; a loop adds 2.
Count each of a set of multiple edges separately.
Check: the sum of the degrees is twice the number of edges.
Watch out for
Counting the loop once gives and a total of 13. An odd total is a sure sign of a mistake.
Counting the two edges between Q and R as one edge.
A graph has five vertices with degrees 1, 2, 3, 3 and 3. How many edges does it have?
Worked example
Using the sum of the degrees
(a) A graph has 6 vertices and 9 edges. Five of the vertices have degrees 2, 3, 3, 4 and 4. Find the degree of the sixth vertex.
(b) Jordan says that a graph can have vertices of degrees 1, 2, 2, 3 and 3. Is Jordan right? Explain.
Step 1: Find the total of the degrees
The sum of the degrees is twice the number of edges: .
Each edge has two ends, and each end adds 1 to the degree of the vertex it meets.
Step 2: Subtract the known degrees
, so the sixth vertex has degree .
Step 3: Add Jordan's degrees
Step 4: Compare with the rule
The sum of the degrees of any graph is , an even number. 11 is odd, so no graph has these degrees. Jordan is wrong.
Another way to say it: every graph has an even number of odd vertices. Jordan's list has three odd degrees (1, 3 and 3).
Try it yourself first, then check the working one step at a time.
Answer
(a) The sixth vertex has degree 2. (b) Jordan is wrong: the degrees add to 11, but the sum of the degrees of any graph is , which is even.
Method
Sum of the degrees the number of edges.
Use it forwards (degrees → edges) or backwards (edges → a missing degree).
An odd total means the graph cannot exist.
Watch out for
Forgetting to double, and using 9 instead of 18 as the degree total.
Definition
Simple graphs and subgraphs
A simple graph has no loops and no multiple edges: each pair of vertices is joined by at most one edge. The Tableland graph is simple; the graph with the loop is not.
A subgraph of a graph is made from some of its vertices and some of its edges. Every edge you keep must keep both of its end vertices, and you cannot add an edge the original graph does not have.
uses only vertices and edges of , so is a subgraph of .
Which of these is not a subgraph of ?
Common mistake
Two counting slips
- Counting a loop once. A loop adds 2 to the degree of its vertex. If your degrees add to an odd number, look for a loop you counted once.
- Counting a crossing as a vertex. Only the dots are vertices. Two edges crossing in a drawing do not meet.
Exam tip
Paper 1 often asks for a degree, a number of edges or a definition. Write the degree total as a check — " ✓" — it takes seconds and catches a missed edge or a loop counted once.
Summary
A graph is vertices (nodes) joined by edges (arcs). Only the connections matter, not how the graph is drawn.
A loop joins a vertex to itself; multiple edges join the same pair of vertices.
The degree of a vertex is the number of edges meeting it, with a loop counted twice.
Sum of the degrees number of edges, so every graph has an even number of odd vertices.
A simple graph has no loops or multiple edges. A subgraph uses some of the vertices and edges of a graph, and nothing else.
Finished the lesson?
Try the 3 quick checks above and the lesson completes itself, or mark it complete now.