AQA A Level Further Maths (Discrete) questions
with solutions
1. What is a connected graph?
2. What is a walk?
3. What is a trail?
4. What is a path?
5. What is a cycle?
1. When there is a path between each pair of vertices.
2. A type of route in a graph. A sequence of edges where you can go
through vertices and edges more than once.
3. A trail is a walk where you can't repeat any edges.
4. A path is a walk where you can't repeat any edges or vertices
5. A cycle is a type of path which starts and ends at the same vertex.
eg. BCDB (don't forget to write B again), and no other vertex is
visited more than once.
1. How would you prove that a graph is Hamiltonian?
2. Connected graphs can be Eulerian, Semi-Eulerian or...
3. What is the number of possible Hamiltonian cycles for a complete
network with n nodes?
4. What are the conditions for an Eulerian graph?
,1. A graph is Hamiltonian if it contains a Hamiltonian Cycle. [1]
Give an example of a Hamiltonian cycle [1]
2. ... Non-Eulerian
3. ½(n-1)! (since route forwards = route backwards)
4. Every vertex is of even degree and the graph is connected
1. What is a subdivision?
2. What is a tree?
3. What is an adjacency matrix?
4. What is a minimum spanning tree?
1. Adding new vertices on an edge, splitting it into 2 edges.
(Don't forget to label the new vertex)
2. A graph with no cycles
3. A table which shows the number of direct connections each vertex
has to the other vertices
4. A spanning tree where the total weight of the arcs is as small as
possible
What are the names for the 2 formula for planar graphs and what are
the formulas?
Euler's formula:
, no of edges = no of vertices + no of faces - 2
Kuratowski's theorum:
A graph is only planar if it does not contain a subgraph that is a
subdivision of K₅ or K₃,₃
1. What is a distance table?
2. How do you do Prim's on a table?
1. A table that shows how each vertex connects directly to every
other vertex, and the weight of the arc. (Not all of the boxes will be
filled as not every network will be complete)
2.
- Label the starting vertex with a 1 and draw a horizontal line
crossing out the rest of the row A
- Looking down the column A, choose the connection with the least
weight and circle it (eg AC).
- Write a 2 on top of the column C, and cross out the row C
- Look down both columns A and C, and circle the connection with
the least weight (eg AD). Write a 3 on top of the D and cross out the
row D.
- Repeat until all nodes are connected
with solutions
1. What is a connected graph?
2. What is a walk?
3. What is a trail?
4. What is a path?
5. What is a cycle?
1. When there is a path between each pair of vertices.
2. A type of route in a graph. A sequence of edges where you can go
through vertices and edges more than once.
3. A trail is a walk where you can't repeat any edges.
4. A path is a walk where you can't repeat any edges or vertices
5. A cycle is a type of path which starts and ends at the same vertex.
eg. BCDB (don't forget to write B again), and no other vertex is
visited more than once.
1. How would you prove that a graph is Hamiltonian?
2. Connected graphs can be Eulerian, Semi-Eulerian or...
3. What is the number of possible Hamiltonian cycles for a complete
network with n nodes?
4. What are the conditions for an Eulerian graph?
,1. A graph is Hamiltonian if it contains a Hamiltonian Cycle. [1]
Give an example of a Hamiltonian cycle [1]
2. ... Non-Eulerian
3. ½(n-1)! (since route forwards = route backwards)
4. Every vertex is of even degree and the graph is connected
1. What is a subdivision?
2. What is a tree?
3. What is an adjacency matrix?
4. What is a minimum spanning tree?
1. Adding new vertices on an edge, splitting it into 2 edges.
(Don't forget to label the new vertex)
2. A graph with no cycles
3. A table which shows the number of direct connections each vertex
has to the other vertices
4. A spanning tree where the total weight of the arcs is as small as
possible
What are the names for the 2 formula for planar graphs and what are
the formulas?
Euler's formula:
, no of edges = no of vertices + no of faces - 2
Kuratowski's theorum:
A graph is only planar if it does not contain a subgraph that is a
subdivision of K₅ or K₃,₃
1. What is a distance table?
2. How do you do Prim's on a table?
1. A table that shows how each vertex connects directly to every
other vertex, and the weight of the arc. (Not all of the boxes will be
filled as not every network will be complete)
2.
- Label the starting vertex with a 1 and draw a horizontal line
crossing out the rest of the row A
- Looking down the column A, choose the connection with the least
weight and circle it (eg AC).
- Write a 2 on top of the column C, and cross out the row C
- Look down both columns A and C, and circle the connection with
the least weight (eg AD). Write a 3 on top of the D and cross out the
row D.
- Repeat until all nodes are connected
