A connected graph with no cycles; n vertices and n-1 edges.

Define a spanning tree.

A subgraph that is a tree and includes every vertex of the graph.

A closed path that starts and ends at the same vertex and visits no other vertex twice.

A graph whose edges have directions, shown by arrows.

When is a graph planar?

When it can be drawn with no edges crossing.

What does isomorphic mean for two graphs?

A one-to-one matching of vertices that preserves every edge.

Condition for a connected graph to be semi-Eulerian?

Exactly two vertices have odd degree; the trail runs from one to the other.

What if a connected graph has four odd vertices?

It is neither Eulerian nor semi-Eulerian.

Why can a graph never have exactly one odd vertex?

The degree sum is twice the number of edges, which is even, so odd vertices come in pairs.

Graph types and Eulerian graphsEdexcel A-Level Further Maths: Flashcards

Card 1 of 140 of 14 known

Question

What is the order (degree) of a vertex?

Tap or press Space to reveal

Tap card or press Space to flip

See all 14 cards

What is the order (degree) of a vertex?: The number of edges meeting at that vertex.
What is the sum of the degrees in a graph?: Twice the number of edges.
Define a tree.: A connected graph with no cycles; $n$ vertices and $n-1$ edges.
Define a spanning tree.: A subgraph that is a tree and includes every vertex of the graph.
What is a cycle?: A closed path that starts and ends at the same vertex and visits no other vertex twice.
What is a digraph?: A graph whose edges have directions, shown by arrows.
How many edges has $K_n$ ?: $\frac{n(n-1)}{2}$
What is the degree of every vertex in $K_n$ ?: $n-1$
When is a graph planar?: When it can be drawn with no edges crossing.
What does isomorphic mean for two graphs?: A one-to-one matching of vertices that preserves every edge.
Condition for a connected graph to be Eulerian?: Every vertex has even degree.
Condition for a connected graph to be semi-Eulerian?: Exactly two vertices have odd degree; the trail runs from one to the other.
What if a connected graph has four odd vertices?: It is neither Eulerian nor semi-Eulerian.
Why can a graph never have exactly one odd vertex?: The degree sum is twice the number of edges, which is even, so odd vertices come in pairs.

Exam questions on Graph types and Eulerian graphs

A simple connected graph has six vertices $A$ , $B$ , $C$ , $D$ , $E$ and $F$ . Its edges are $AB$ , $AC$ , $BC$ , $BD$ , $CE$ , $DE$ , $DF$ and $EF$ .
The edge $BE$ is added to the graph. Explain why the new graph is semi-Eulerian.2 marks
The complete graph $K_n$ has $n$ vertices, and every pair of distinct vertices is joined by exactly one edge.
Given that $K_n$ has 45 edges, find the value of $n$ .2 marks
A weighted network has five vertices $P$ , $Q$ , $R$ , $S$ and $T$ . Its edges and weights are $PQ=5$ , $PR=3$ , $QR=4$ , $QS=6$ , $RS=2$ , $RT=7$ and $ST=4$ .
Explain what is meant by a spanning tree of this network, and state how many edges every spanning tree of it contains.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).