QCAA General Mathematics Graphs and networks
5 sample questions with marking guides and sample answers
A connected graph has six vertices and six edges.
How many of the following four statements must always be true?
- the graph has no vertices of odd degree
- the graph contains a Eulerian trail
- the graph contains a Hamiltonian path
- the sum of the degrees of the vertices is 12
1
2
3
4
Reveal Answer
1
Only one statement is always true: the sum of the degrees is 12. By the Handshaking Lemma, the sum of degrees is always twice the number of edges (). The other statements can be disproven with counterexamples.
2
Only one statement is always true. A graph consisting of a triangle with three separate edges attached to its vertices has degrees of 3, 3, 3, 1, 1, and 1, which disproves the first three statements.
3
Only one statement is always true. A connected graph with 6 vertices and 6 edges does not necessarily have a Eulerian trail or a Hamiltonian path, nor does it require all even degrees.
4
It is impossible for all four statements to always be true. Only the statement regarding the sum of the degrees being 12 is a universal property of any graph with 6 edges.
In a graph, an open walk with repeated vertices and no repeated edges is called a
bridge.
loop.
path.
trail.
Reveal Answer
bridge.
A bridge is a specific type of edge whose removal increases the number of connected components in a graph, not a type of walk.
loop.
A loop is an edge that connects a vertex to itself, rather than a sequence of vertices and edges known as a walk.
path.
A path is a walk where all vertices must be distinct. Since the question specifies that vertices are repeated, it cannot be a path.
trail.
A trail is defined as a walk in which no edges are repeated, but vertices are allowed to be repeated.
A bipartite graph is typically used to display which one of the following?
the allocation of tasks on a construction site
the path used to visit five different construction sites
the total distance travelled between two construction sites
the critical path of activities to be completed in a construction project
the minimum length of cable required to connect six construction sites
Reveal Answer
the allocation of tasks on a construction site
Bipartite graphs are ideal for modeling assignment problems, such as allocating a set of workers to a set of tasks, where edges connect the two distinct groups.
the path used to visit five different construction sites
Finding a path to visit multiple sites is a routing problem (like the Travelling Salesperson Problem), which is typically modeled using a complete or general graph.
the total distance travelled between two construction sites
Determining the distance between two sites is a shortest path problem, which is best modeled using a weighted graph rather than a bipartite graph.
the critical path of activities to be completed in a construction project
Critical path analysis for project activities is modeled using a directed acyclic graph (DAG) or an activity network, as it requires showing dependencies and sequence.
the minimum length of cable required to connect six construction sites
Finding the minimum cable to connect multiple sites is a minimum spanning tree problem, which is modeled using a weighted graph.
Identify the number of faces for a planar graph that has 5 edges and 3 vertices.
8
6
4
2
Reveal Answer
8
Incorrect. This incorrectly adds the number of vertices and edges () instead of applying Euler's formula.
6
Incorrect. This is a miscalculation; applying Euler's formula () with and does not result in 6 faces.
4
Correct. By Euler's formula for planar graphs (), substituting and gives , which means there are faces.
2
Incorrect. This is the constant value in Euler's formula (), not the calculated number of faces.
A basketball competition has six teams that have completed three rounds of competition as shown.
| Bears | Eagles | Lions | Meerkats | Tigers | Wombats | |
|---|---|---|---|---|---|---|
| Bears | — | — | ✓ | — | ✓ | ✓ |
| Eagles | — | — | ✓ | ✓ | — | ✓ |
| Lions | ✓ | ✓ | — | ✓ | — | — |
| Meerkats | — | ✓ | ✓ | — | ✓ | — |
| Tigers | ✓ | — | — | ✓ | — | ✓ |
| Wombats | ✓ | ✓ | — | — | ✓ | — |
The graph to represent this information has
6 edges.
9 edges.
15 edges.
18 edges.
Reveal Answer
6 edges.
This number corresponds to the number of vertices (teams) in the graph, not the number of edges (games played).
9 edges.
The table contains 18 checkmarks total. Since each game involves two teams and is recorded for both, the number of edges is half the total count: .
15 edges.
This would be the number of edges if every team played every other team (a complete graph ), calculated as .
18 edges.
This is the total number of checkmarks in the table. Because the graph is undirected (Team A vs Team B is the same game as Team B vs Team A), you must divide this sum by 2.