7.02a–7.02c - Graph terminology and notation | OCR A-Level Further Mathematics A

Learn the language that describes connections without measuring their lengths or angles. In $7.02a$ you will describe vertices, arcs and degrees; in $7.02b$ you will recognise simple graphs, connected graphs and trees; in $7.02c$ you will distinguish the different kinds of route through a graph.

Vertices and arcs

Two drawings show five dots joined by the same six connections. One looks like a square with a tail; the other looks like tangled string. Can they describe exactly the same mathematical object? Yes: a graph records which objects are connected, rather than where you draw them. We will finish by describing a journey in this language, without needing any lengths or angles.

Suppose the objects are $A, B, C, D, E$ , with connections $AB, BC, CD, DA, AC, CE$ . You can move the dots, stretch the lines or bend them. Keep these six connections and you keep the graph. A crossing is not an extra dot unless a vertex is actually marked there.

[DIAGRAM: asset_name: Connections rather than positions; asset_slug: h245_7_02_same_connections; caption: Two drawings have the same five vertices and six arcs; crossings without a marked dot are not vertices; description: Two panels show the graph with vertices A B C D E and edges AB BC CD DA AC CE in different layouts. A central comparison lists the same six connections. A crossing in the second panel is unmarked and explicitly labelled not a vertex.]
Two drawings have the same five vertices and six arcs

Vertices, arcs and adjacency

A graph consists of vertices and arcs joining them. A vertex is also called a node; an arc is also called an edge. An arc is incident with each of its end vertices. Two vertices are adjacent if an arc joins them; two distinct arcs are adjacent if they share an end vertex. A loop is an arc whose two ends are the same vertex. Multiple arcs join the same pair of vertices more than once.

For the graph above, $A$ and $C$ are adjacent, and $AB$ and $AC$ are adjacent arcs because both are incident with $A$ . The arcs $AB$ and $CD$ are not adjacent, even if they cross in a drawing. A triangle is a cycle made from three arcs; it is not a loop. These definitions are not supplied in the formula booklet.

Key idea

A graph preserves connections. A crossing, a bend or a change of scale does not change those connections.

Use the end vertices, rather than the appearance of the lines, in this check.

Degrees and counting arcs

The degree of a vertex counts the ends of arcs that meet it. Each ordinary arc contributes one at each end; a loop contributes two at its single vertex, because both of its ends are there.

Degree

The degree of a vertex $v$ , written $\deg v$ , is the number of incident arc ends, counting a loop twice and counting each multiple arc separately. An isolated vertex has degree $0$ . A degree sequence is the list of all vertex degrees, usually written in decreasing order.

Counting at every vertex counts every arc twice. For the opening graph the degrees are $3, 2, 4, 2, 1$ , whose sum is $12$ , twice its six arcs. This gives a useful result even when the graph is too large to draw.

Degree sum

For a finite undirected graph with $E$ arcs,

\sum_v \deg v = 2E

Consequently, the number of vertices of odd degree is even: an even total cannot contain an odd number of odd summands.
Not in the formula booklet: learn it.

The result counts loops correctly only if their two ends are both included in the degree.

Worked example 1: reading an arc list

Question. A graph has vertices $A, B, C, D, E$ and arcs $AB, AC, BC, CD, DE$ . State its degree sequence and verify the degree-sum result.

Plan. Count the arcs incident with each vertex, then add the degrees.

\begin{aligned} (\deg A,\deg B,\deg C,\deg D,\deg E)&=(2,2,3,2,1) && \text{count incident ends}\\ \text{degree sequence}&=(3,2,2,2,1) && \text{put in decreasing order}\\ 3+2+2+2+1&=10=2\times5 && \text{five arcs} \end{aligned}

Why this step? Count at the labelled vertices first; sorting too early makes it easier to miss a connection.

Answer. The degree sequence is $(3,2,2,2,1)$ , with sum twice the number of arcs.

Check. Exactly two vertices, $C$ and $E$ , have odd degree.

The second example changes one feature: one extra arc is a loop. Its contribution to the degree is two, not one.

Worked example 2: adding a loop

Question. The graph in Worked example 1 gains a loop at $C$ . State the new degree sequence and number of arcs.

Plan. Increase $\deg C$ by two, leaving all other degrees unchanged.

\begin{aligned} \deg C&=3+2=5 && \text{both loop ends meet }C\\ \text{degree sequence}&=(5,2,2,2,1) && \text{other degrees unchanged}\\ E&=\frac{5+2+2+2+1}{2}=6 && \text{degree sum} \end{aligned}

Why this step? The loop is one extra arc but contributes two extra incident ends.

Answer. The sequence is $(5,2,2,2,1)$ , and there are $6$ arcs.

Check. The original five arcs plus one loop give six arcs directly.

Degree sums provide a quick check, but an even sum alone does not prove that a proposed sequence is possible for a simple graph.

Watch out

Wrong: “A loop adds $1$ to the degree.” It adds $2$ . Also, $(4,1,1,0)$ has even sum but cannot be the degree sequence of a simple graph on four vertices: a vertex can have at most three distinct neighbours.

Try a different extra arc, this time joining two different vertices that were already adjacent.

Simple graphs, connected graphs and trees

Three different restrictions answer three different questions: are connections repeated, can every vertex be reached, and are there any closed circuits?

Simple and connected graphs

A simple graph has no loops and no multiple arcs. A graph is connected if there is a path between every pair of vertices. In this course simply connected means both simple and connected. A tree is a connected graph with no cycles.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

Last Accessed

Pure Core

Statistics

Mechanics

Discrete Mathematics

Additional Pure Mathematics

7.02a–7.02c - Graph terminology and notation

Vertices and arcs

Degrees and counting arcs

Simple graphs, connected graphs and trees

Continue this lesson.

Learn faster with Nova