A walk in which no edge is repeated.

A walk in which no vertex is repeated.

A closed path: it starts and ends at the same vertex and repeats no other vertex.

What does connected mean?

There is a path between every pair of vertices.

What is a subdivision of an edge?

Replacing an edge with a path through a new vertex, which adds one vertex and one edge.

When is a connected graph Eulerian?

When every vertex has even degree.

When is a connected graph semi-Eulerian?

When exactly two vertices have odd degree.

Where must a semi-Eulerian trail start and finish?

At the two odd-degree vertices.

What is a Hamiltonian cycle?

A cycle that passes through every vertex exactly once.

Why can't a vertex of degree 1 be on a cycle?

A cycle needs two edges at every vertex it passes through.

How many odd vertices can a graph have?

An even number, because the sum of degrees is even.

Language and properties of graphsAQA A-Level Further Maths: Flashcards

Card 1 of 130 of 13 known

Question

What is the degree of a vertex?

Tap or press Space to reveal

Tap card or press Space to flip

See all 13 cards

What is the degree of a vertex?: The number of edge-ends at the vertex; a loop counts twice.
What is the sum of the degrees of all vertices?: Twice the number of edges.
What is a trail?: A walk in which no edge is repeated.
What is a path?: A walk in which no vertex is repeated.
What is a cycle?: A closed path: it starts and ends at the same vertex and repeats no other vertex.
What does connected mean?: There is a path between every pair of vertices.
What is a subdivision of an edge?: Replacing an edge with a path through a new vertex, which adds one vertex and one edge.
When is a connected graph Eulerian?: When every vertex has even degree.
When is a connected graph semi-Eulerian?: When exactly two vertices have odd degree.
Where must a semi-Eulerian trail start and finish?: At the two odd-degree vertices.
What is a Hamiltonian cycle?: A cycle that passes through every vertex exactly once.
Why can't a vertex of degree 1 be on a cycle?: A cycle needs two edges at every vertex it passes through.
How many odd vertices can a graph have?: An even number, because the sum of degrees is even.

Exam questions on Language and properties of graphs

A graph $G$ has vertices $A,\ B,\ C,\ D,\ E$ and seven edges: $AB$ , $AC$ , $BC$ , $BD$ , $CD$ , $CE$ and $DE$ .
Write down a trail in $G$ that uses every edge exactly once.2 marks
A graph $H$ has vertices $P,\ Q,\ R,\ S,\ T,\ U$ and eight edges: $PQ$ , $QR$ , $RS$ , $ST$ , $TU$ , $UP$ , $PS$ and $QT$ .
Explain why $H$ is neither Eulerian nor semi-Eulerian.2 marks
A connected simple graph $K$ has six vertices. Five of the vertices have degrees $2,\ 2,\ 3,\ 3$ and $4$ , and the sixth vertex has degree $x$ .
Show that $x$ is even, and state with a reason whether $K$ is Eulerian, semi-Eulerian or neither.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).