Counting a loop once
A loop has both of its ends at the same vertex, so it adds 2 to that vertex's degree. (In an adjacency matrix, though, a loop is entered as 1.)
General Mathematics · Unit 4 · Topic 3
Describe graphs with vertices, edges and degrees, build network diagrams and adjacency matrices from real situations, use Euler's formula for planar graphs, and find shortest paths, Eulerian trails and Hamiltonian cycles.
Read a graph as vertices joined by edges, find the degree of every vertex — counting a loop twice — and use the sum of the degrees to count edges.
Recognise complete, bipartite, directed and weighted graphs, and construct a network diagram for a real situation such as walking tracks, a social network, one-way streets or a round-robin.
Store a graph or digraph as an adjacency matrix, read degrees and edge counts from the matrix, and draw the graph that a matrix describes.
Decide whether a graph is planar by redrawing it without crossings, count its faces, and use Euler's formula to find a missing count or test a claim.
Describe routes through a graph precisely — walks, trails and paths, open or closed, circuits and cycles — and recognise connected graphs and bridges.
Find the shortest path between two vertices of a weighted graph by listing the possible routes systematically, totalling each, and choosing the least.
Use the degrees of the vertices to decide whether a graph is Eulerian, semi-Eulerian or neither, find Eulerian trails and circuits, and solve route problems that must cover every edge.
Find routes that visit every vertex exactly once, decide whether a graph is Hamiltonian or semi-Hamiltonian, and find the shortest Hamiltonian cycle in a small network by trial and error.
Ten questions across the topic, from foundation to complex unfamiliar. Your results feed your mastery.
A road map, a rail map, a group chat and a sports draw all have the same skeleton: things, and connections between them. A graph keeps only that skeleton — dots for the things, lines for the connections — so you can reason about it without the clutter.
In this topic you learn the language of graphs, store them as adjacency matrices, and use Euler's formula on graphs drawn without crossings. Then you put graphs to work: finding the shortest route between two towns, deciding whether a street sweeper can cover every street exactly once, and planning a delivery run that visits every stop once and returns home.
Almost everything here is reasoning and careful counting rather than calculation, so the marks go to clear working: name the vertices you used, show the totals you compared, and justify each decision with degrees.
Builds on Matrices.
Subject matter from the General Mathematics General senior syllabus 2025 v1.3 (opens in a new tab), CC BY 4.0 © State of Queensland (QCAA).
The focus areas you can practise on their own. Each one maps to dot points above.
Graph vocabulary
Vertices, edges, loops, simple graphs and subgraphs — say what each term means and spot it in a drawing.
Degrees of vertices
Find the degree of a vertex (a loop counts twice) and use the sum of the degrees to count edges.
Types of graphs
Complete, bipartite, directed and weighted graphs and networks, including counting the edges of a complete graph.
Drawing network diagrams
Turn a table or a description of a real situation into a graph, digraph or weighted network.
Adjacency matrices
Build the adjacency matrix of a graph or digraph, and draw the graph a matrix describes.
Planar graphs and faces
Decide whether a graph can be drawn without crossings, and count its faces, including the outside one.
Euler's formula
Use v + f − e = 2 to find a missing count or to test whether a planar graph is possible.
Walks, trails, paths and cycles
Classify a route as a walk, trail, path, circuit or cycle, and recognise connected graphs and bridges.
Shortest paths by trial and error
Find the route of least total weight between two vertices by listing and comparing routes.
Eulerian trails and circuits
Use degrees to decide whether a graph is Eulerian or semi-Eulerian, and plan routes that use every edge once.
Hamiltonian paths and cycles
Find routes that visit every vertex exactly once, and the shortest such cycle, by trial and error.
A loop has both of its ends at the same vertex, so it adds 2 to that vertex's degree. (In an adjacency matrix, though, a loop is entered as 1.)
The unbounded region around a planar drawing is a face. Leave it out and comes to 1 instead of 2.
Where two edges cross in a drawing there is no vertex unless a dot is drawn there — think of a road overpass, not an intersection.
Eulerian routes use every edge exactly once, and degrees decide whether one exists. Hamiltonian routes visit every vertex exactly once, and you check by trial and error.
In a semi-Eulerian graph, an Eulerian trail must start at one of the two odd vertices and finish at the other. Start anywhere else and you get stuck.
The shortest path has the least total weight. It can pass through more vertices than a route that looks more direct.
A cycle repeats no vertex except the start. –––––– passes through in the middle, so it is a circuit but not a cycle.
Rows are "from" and columns are "to": the entry in row , column counts arcs from to . Label both and check one arc against the drawing.
holds for a connected graph drawn without crossings. Count faces only in a planar drawing.
Justify Eulerian decisions with degrees: name the odd vertices. "B and E have odd degree and the rest are even, so the graph is semi-Eulerian; the trail starts at B and finishes at E, or the reverse."
Write routes as vertex sequences, such as ––– or ACBD, and give every total with its unit (km, min, $).
"By trial and error" still needs working: list the routes you compared with their totals, then state the shortest.
Label the rows and the columns of an adjacency matrix with the vertices, in the same order.
In Euler's formula questions, write down , and before substituting, and count the outside face. The formula is in the QCAA formula book; the Eulerian conditions are not.
Check any network you draw against the information given: count the edges, and confirm the degrees add to .
A vertex of degree 2 forces both of its edges into any Hamiltonian cycle. Use this to cut down your trial and error.
Read whether the route must return to its start (circuit or cycle) or not (trail or path) before you start.
Navigation apps find shortest paths through road networks, with weights for distance, time or tolls.
Councils plan street sweeping, rubbish collection and line marking so that every street is covered with as little doubling back as possible — an Eulerian problem.
Couriers, technicians and tour operators plan runs that visit every stop once and return to base — a Hamiltonian problem.
Printed circuit boards and underground services are laid out so that connections do not cross, which is a question about planar graphs.
Social networks are graphs of people and connections; people with a high degree are the most connected.
Round-robin sports draws are complete graphs, and the results form a digraph with an arrow from each winner to the loser.
Computers store networks as adjacency matrices, and powers of the matrix count two-step and three-step links (Unit 2 Matrices).