Foundation to VCE • Explore the maths library • Try a free sample
VCE Specialist Mathematics Units 1–2 · Algebra, number and structure

Teach graph theory and structural proofs.

The handshaking lemma counts every undirected edge at both ends: the sum of degrees is 2 E. A loop contributes 2 to its vertex degree.

View worksheets & preview

Aspire to Power Learning · https://resources.aspiretopowerlearning.com.au/home-learning/topics/specialist-1-2-graph-theory/

Check the starting point

  • Count degrees, treating loops as two incidences.
  • Use parity and simple counting arguments.

Show the idea

Degrees count both ends of every edge

Degrees are A:3, B:2, C:2, D:1. Their sum is 8=2E. The two odd vertices A and D illustrate the parity result.
Select the diagram to view it at full size.

Degrees are A:3, B:2, C:2, D:1. Their sum is 8=2E. The two odd vertices A and D illustrate the parity result.

Work through an example

How many edges does the complete graph K_6 have?

  1. In K_6, every pair of distinct vertices is connected by exactly one edge.
  2. Each of the 6 vertices has degree 5. The sum of the degrees is 6×5=30.
  3. Each edge contributes to two vertex degrees, so E=30/2=15. Equivalently, choose an unordered pair: C(6,2)=15.

Answer: 15.

Teach in small steps

  1. Read the visual model together: Degrees are A:3, B:2, C:2, D:1. Their sum is 8=2E. The two odd vertices A and D illustrate the parity result.
  2. Model this example aloud: How many edges are in K_7 and K_(2,5)? Guide: A complete graph has C(7,2)=21 edges; a complete bipartite graph has one edge for each cross-part pair, 2×5. Result: 21 and 10.
  3. Let your learner choose the steps for a new situation: Use the planar bipartite bound E≤2V−4 to show K_(3,3) is not planar. 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 connected planar graph has 9 vertices and 14 edges. Find the number of faces, including the outside face. Compare both the method and conclusion with the checkpoint answers, then revisit any misconception.

Ask and listen

  • A 4-regular undirected graph has 10 vertices. Find its edge count.
  • Can an undirected graph have degree sequence 3,3,3,2? Explain.

Adapt the practice

More support

Start with this prerequisite: Count degrees, treating loops as two incidences. Keep the visual visible. For the first guided problem, focus on this step: A complete graph has C(7,2)=21 edges; a complete bipartite graph has one edge for each cross-part pair, 2×5.

More challenge

Try this application without looking at its answer: A connected graph has 9 vertices and 8 edges. Prove that it has no cycle. 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 connected planar graph has 9 vertices and 14 edges. Find the number of faces, including the outside face.
  • Your learner can justify or challenge this statement/question using the mathematical definitions: Can an undirected graph have degree sequence 3,3,3,2? Explain.

Choose the next step

If either checkpoint needs prompting, repeat the worked model with changed values and revisit this caution: A loop contributes two to the degree of its vertex. 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