Vertices (nodes) joined by edges (arcs).

What is a weighted graph?

A graph with a number (weight) on each edge, also called a network.

What is the degree of a vertex?

The number of edges meeting at the vertex, also called its valency.

A finite sequence of edges where the end vertex of one edge is the start of the next.

A walk in which no vertex is repeated.

A closed path, starting and ending at the same vertex.

What is a connected graph?

A graph in which every pair of vertices is joined by a path.

A connected graph with no cycles.

What is a spanning tree?

A subgraph that is a tree and includes all the vertices.

What are the edges and vertex degree in a complete graph on n vertices?

\frac{n(n-1)}{2} edges; every degree is n-1.

Graph theory terminologyEdexcel International A Level Maths: Flashcards

Card 1 of 130 of 13 known

Question

What is a graph?

Tap or press Space to reveal

Tap card or press Space to flip

See all 13 cards

What is a graph?: Vertices (nodes) joined by edges (arcs).
What is a weighted graph?: A graph with a number (weight) on each edge, also called a network.
What is the degree of a vertex?: The number of edges meeting at the vertex, also called its valency.
What is the sum of the degrees of a graph?: Twice the number of edges.
How many odd vertices can a graph have?: An even number.
What is a walk?: A finite sequence of edges where the end vertex of one edge is the start of the next.
What is a path?: A walk in which no vertex is repeated.
What is a cycle?: A closed path, starting and ending at the same vertex.
What is a connected graph?: A graph in which every pair of vertices is joined by a path.
What is a tree?: A connected graph with no cycles.
How many edges does a tree with $n$ vertices have?: $n-1$
What is a spanning tree?: A subgraph that is a tree and includes all the vertices.
What are the edges and vertex degree in a complete graph on $n$ vertices?: $\frac{n(n-1)}{2}$ edges; every degree is $n-1$ .

Exam questions on Graph theory terminology

A graph $G$ has vertices $A, B, C, D, E$ and edges $AB$ , $AC$ , $BC$ , $CD$ and $DE$ .
State, with a reason, whether $G$ is a tree.2 marks
$K$ is the complete graph with 6 vertices.
A spanning tree of $K$ is formed by deleting edges. State the number of edges in the spanning tree and the number of edges deleted.2 marks
A graph $H$ has vertices $P, Q, R, S, T, U$ and edges $PQ$ , $QR$ , $RS$ , $ST$ , $TU$ , $UP$ and $QT$ .
(i) Write down a cycle in $H$ that contains exactly four vertices. (ii) Write down a walk in $H$ of five edges that is not a path.3 marks

See the full worksheet

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).