General Mathematics · Unit 4 · Topic 3

Graphs and networks

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.

  • 8 lessons
  • 2 h 13 min of lessons
  • 16 worked examples
  • 12 hours in the syllabus
0 of 8

Start here

Graphs, vertices, edges and degree

Lesson 1 of 8 · 16 min

Start the topic

Lessons

8
  1. Graphs, vertices, edges and degree (up next)

    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.

  2. Types of graphs and network diagrams

    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.

  3. Adjacency matrices

    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.

  4. Planar graphs and Euler's formula

    Decide whether a graph is planar by redrawing it without crossings, count its faces, and use Euler's formula v+f−e=2v + f - e = 2 to find a missing count or test a claim.

  5. Walks, trails, paths, circuits and cycles

    Describe routes through a graph precisely — walks, trails and paths, open or closed, circuits and cycles — and recognise connected graphs and bridges.

  6. Shortest paths by trial and error

    Find the shortest path between two vertices of a weighted graph by listing the possible routes systematically, totalling each, and choosing the least.

  7. Eulerian trails and circuits

    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.

  8. Hamiltonian paths and cycles

    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.

  9. Topic quiz

    Ten questions across the topic, from foundation to complex unfamiliar. Your results feed your mastery.

About this topic

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 v+f−e=2v + f - e = 2 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.

Before you start

Builds on Matrices.

  • Reading matrices: rows, columns, entries and the size of a matrix (Unit 2, Matrices).
  • Adding whole numbers and decimals accurately — a route's length is the sum of its edge weights.
  • Speed, distance and time, s=dts = \frac{d}{t}, for turning a route length into a travel time.

What QCAA says you need to know13 dot points

Graphs, associated terminology and the adjacency matrix

4 hours

Planar graphs, paths and cycles

8 hours

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.

    Practise
  • Degrees of vertices

    Find the degree of a vertex (a loop counts twice) and use the sum of the degrees to count edges.

    Practise
  • Types of graphs

    Complete, bipartite, directed and weighted graphs and networks, including counting the edges of a complete graph.

    Practise
  • Drawing network diagrams

    Turn a table or a description of a real situation into a graph, digraph or weighted network.

    Practise
  • Adjacency matrices

    Build the adjacency matrix of a graph or digraph, and draw the graph a matrix describes.

    Practise
  • Planar graphs and faces

    Decide whether a graph can be drawn without crossings, and count its faces, including the outside one.

    Practise
  • Euler's formula

    Use v + f − e = 2 to find a missing count or to test whether a planar graph is possible.

    Practise
  • Walks, trails, paths and cycles

    Classify a route as a walk, trail, path, circuit or cycle, and recognise connected graphs and bridges.

    Practise
  • Shortest paths by trial and error

    Find the route of least total weight between two vertices by listing and comparing routes.

    Practise
  • Eulerian trails and circuits

    Use degrees to decide whether a graph is Eulerian or semi-Eulerian, and plan routes that use every edge once.

    Practise
  • Hamiltonian paths and cycles

    Find routes that visit every vertex exactly once, and the shortest such cycle, by trial and error.

    Practise

Worked examples16

All 16

Common mistakes

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.)

Forgetting the outside face

The unbounded region around a planar drawing is a face. Leave it out and v+f−ev + f - e comes to 1 instead of 2.

Treating a crossing as a vertex

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.

Mixing up Eulerian and Hamiltonian

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.

Starting an Eulerian trail anywhere

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.

Choosing the route with the fewest edges

The shortest path has the least total weight. It can pass through more vertices than a route that looks more direct.

Calling every closed trail a cycle

A cycle repeats no vertex except the start. BB–CC–EE–BB–AA–FF–BB passes through BB in the middle, so it is a circuit but not a cycle.

Reading a digraph's matrix the wrong way round

Rows are "from" and columns are "to": the entry in row PP, column QQ counts arcs from PP to QQ. Label both and check one arc against the drawing.

Using Euler's formula where it does not apply

v+f−e=2v + f - e = 2 holds for a connected graph drawn without crossings. Count faces only in a planar drawing.

Exam tips

  1. 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."

  2. Write routes as vertex sequences, such as AA–CC–BB–DD or ACBD, and give every total with its unit (km, min, $).

  3. "By trial and error" still needs working: list the routes you compared with their totals, then state the shortest.

  4. Label the rows and the columns of an adjacency matrix with the vertices, in the same order.

  5. In Euler's formula questions, write down vv, ff and ee before substituting, and count the outside face. The formula is in the QCAA formula book; the Eulerian conditions are not.

  6. Check any network you draw against the information given: count the edges, and confirm the degrees add to 2e2e.

  7. A vertex of degree 2 forces both of its edges into any Hamiltonian cycle. Use this to cut down your trial and error.

  8. Read whether the route must return to its start (circuit or cycle) or not (trail or path) before you start.

Where this shows up

  • 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).

Save your progress with a free account