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 PP, and two edges joining QQ and RR.

Definition

Degree of a vertex

The degree of a vertex, written deg⁡(A)\deg(A), 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, QQ meets one edge to PP, two edges to RR and one edge to SS, so deg⁡(Q)=4\deg(Q) = 4. Each of the multiple edges counts separately.

In the graph with the loop, what is deg⁡(P)\deg(P)?

Interactive

Count the degrees

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 3+3+2+2+2+2+2=163 + 3 + 2 + 2 + 2 + 2 + 2 = 16, and the graph has 8 edges: 16=2×816 = 2 \times 8. That is no coincidence.

Key idea

The sum of the degrees

In every graph,

sum of the degrees of all the vertices=2×number of edges\text{sum of the degrees of all the vertices} = 2 \times \text{number of edges}

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 2e2e, 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

  • Simple familiar

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.

5 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Count the edge-ends at each vertex; a loop adds 2.

  2. Count each of a set of multiple edges separately.

  3. Check: the sum of the degrees is twice the number of edges.

Watch out for

  • Counting the loop once gives deg⁡(P)=3\deg(P) = 3 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

  • Complex familiar

(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.

4 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Sum of the degrees =2×= 2 \times the number of edges.

  2. Use it forwards (degrees → edges) or backwards (edges → a missing degree).

  3. 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.

HH uses only vertices and edges of GG, so HH is a subgraph of GG.

Which of these is not a subgraph of GG?

Choose one answer

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 — "sum of degrees=14=2×7\text{sum of degrees} = 14 = 2 \times 7 ✓" — 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 =2×= 2 \times 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.

Lesson 1 of 80% read

Save your progress with a free account