AQA A-LEVEL FURTHER
MATHEMATICS 7367-3M PAPER 3
MECHANICS MARK SCHEME JUNE
2025 | LATEST UPDATED.
Euler's formula
v-e+f=2
Walk
A walk is a set of edges joined end to end, so the end vertex of one edge is the start vertex of the
next.
Trail
A trail is a walk in which no edges are repeated. Vertices can be repeated in a trail, though they are
often not.
Cycle
A cycle is a trail which starts and finishes at the same vertex. Other than the start being the same as
the finish, vertices are not repeated in a cycle.
Subgraph
A subgraph of a graph is formed by using some or all of the vertices of a graph together with some or
all the edges that connect these vertices. A subgraph is a graph contained within another graph. This
could result in an unconnected vertex. However, subgraphs are usually connected.
Subdivision
Subdivision means inserting a vertex of degree 2 into an edge. Subdivision increases the number of
vertices by 1 and the number of edges by 1.
Connected graph
A graph is connected if it is possible to get from any vertex to another, directly or indirectly.
Simple graph
A graph with no loops and no multiple edges is called a simple graph.
How many edges does K_n have?
1/2n(n-1)
Complete graph
A simple graph, on a given number of vertices, with the maximum possible number of edges is called
a complete graph. Each vertex is connected by a single edge to each of the other vertices.
Complete bipartite graph
MATHEMATICS 7367-3M PAPER 3
MECHANICS MARK SCHEME JUNE
2025 | LATEST UPDATED.
Euler's formula
v-e+f=2
Walk
A walk is a set of edges joined end to end, so the end vertex of one edge is the start vertex of the
next.
Trail
A trail is a walk in which no edges are repeated. Vertices can be repeated in a trail, though they are
often not.
Cycle
A cycle is a trail which starts and finishes at the same vertex. Other than the start being the same as
the finish, vertices are not repeated in a cycle.
Subgraph
A subgraph of a graph is formed by using some or all of the vertices of a graph together with some or
all the edges that connect these vertices. A subgraph is a graph contained within another graph. This
could result in an unconnected vertex. However, subgraphs are usually connected.
Subdivision
Subdivision means inserting a vertex of degree 2 into an edge. Subdivision increases the number of
vertices by 1 and the number of edges by 1.
Connected graph
A graph is connected if it is possible to get from any vertex to another, directly or indirectly.
Simple graph
A graph with no loops and no multiple edges is called a simple graph.
How many edges does K_n have?
1/2n(n-1)
Complete graph
A simple graph, on a given number of vertices, with the maximum possible number of edges is called
a complete graph. Each vertex is connected by a single edge to each of the other vertices.
Complete bipartite graph
