Foundation to VCE • Explore the maths library • Try a free sample
VCE General Mathematics Units 1–2 · Discrete mathematics

Teach graphs, paths and minimum connectors.

Graphs represent objects as vertices and connections as edges. A path does not repeat vertices; a trail does not repeat edges.

View worksheets & preview

Aspire to Power Learning · https://resources.aspiretopowerlearning.com.au/home-learning/topics/general-1-2-graphs-networks/

Check the starting point

  • Count edges incident to each vertex.
  • Add positive route weights without repeating unintended edges.

Show the idea

A small weighted network

AB, BC and CD connect all four vertices with total weight 5. The route A–B–C–D also has length 5 in this example; the two optimisation goals differ in general.
Select the diagram to view it at full size.

AB, BC and CD connect all four vertices with total weight 5. The route A–B–C–D also has length 5 in this example; the two optimisation goals differ in general.

Work through an example

A connected planar graph has 6 vertices and 8 edges. Find faces.

  1. For a connected planar graph, Euler's relation is V-E+F=2; F includes the unbounded outside face.
  2. Substitute V=6 and E=8: 6-8+F=2, so -2+F=2.
  3. Add 2 to both sides to obtain F=4. Three bounded faces plus the outside face would make four in total.

Answer: 4.

Teach in small steps

  1. Read the visual model together: AB, BC and CD connect all four vertices with total weight 5. The route A–B–C–D also has length 5 in this example; the two optimisation goals differ in general.
  2. Model this example aloud: An undirected graph has edges AB, BC, CA and AD. Give all degrees and check the handshaking lemma. Guide: Every edge contributes one degree at each endpoint. Result: A=3, B=2, C=2, D=1; degree sum 8=2×4.
  3. Let your learner choose the steps for a new situation: For undirected edges AB=3, AC=9, BC=2, BD=6 and CD=1, find a shortest A-to-D route. Ask which part of the model or rule carries over before checking the worked solution.
  4. After a short break, ask for an independent response: A tree has 15 edges. How many vertices does it have? Compare both the method and conclusion with the checkpoint answers, then revisit any misconception.

Ask and listen

  • A connected planar graph has 8 vertices and 11 edges. Find its number of faces, including the outside face.
  • The sequence A–B–C–A uses three different edges of a triangle. Is it a trail? Is it a path under the no-repeated-vertices definition?

Adapt the practice

More support

Start with this prerequisite: Count edges incident to each vertex. Keep the visual visible. For the first guided problem, focus on this step: Every edge contributes one degree at each endpoint.

More challenge

Try this application without looking at its answer: For the same network, give a minimum spanning tree and its total weight. Then explain why the answer fits the stated domain or context.

Look for understanding

  • Your learner can complete this checkpoint and explain the method: A tree has 15 edges. How many vertices does it have?
  • Your learner can justify or challenge this statement/question using the mathematical definitions: The sequence A–B–C–A uses three different edges of a triangle. Is it a trail? Is it a path under the no-repeated-vertices definition?

Choose the next step

If either checkpoint needs prompting, repeat the worked model with changed values and revisit this caution: A minimum spanning tree minimises total connecting cost; it does not generally provide every shortest route. When both are secure, use the linked Apply and extend resource and relevant VCE Key Knowledge/Key Skills activity.

Put the idea into practice

The matching topic collection includes learn-and-practise, application and checkpoint PDFs with worked answers. Download the free preview to see representative pages.

Explore this topic’s worksheets