Graphs (Edexcel A-Level Further Mathematics): Revision Notes

Example:

For a square with a diagonal :

Example 1: Checking Planarity of a Graph

Problem:

Determine if the following graph is planar:

• Vertices: $A, B, C, D, E$
• Edges: $AB, BC, CD, DA, AC, BD$

Step 1: Count Vertices and Edges:

$v = 5, e = 6$

Step 2: Check for Subgraph Homeomorphic to $K_5$:

This graph is not $K_5$

Step 3: Apply Euler's Formula:

Assuming planarity: $v - e + f = 2$

The graph satisfies Euler's formula

Conclusion:

The graph is planar because it does not contain $K_5$ or $K_{3,3}$, and it satisfies Euler's formula.

Example 2: Checking a Non-Planar Graph

Problem:

Determine if $K_{3,3}$ is planar.

Step 1: Count Vertices and Edges:

$v = 6, e = 9$

Step 2: Apply Euler's Formula:

Assuming planarity: $v - e + f = 2$

This value is valid, so proceed to check for subgraphs

Step 3: Check for Crossings:

$K_{3,3}$ cannot be drawn without edges crossing (proved mathematically).

Conclusion:

$K_{3,3}$ is non-planar because it cannot be drawn without overlapping edges.

Common Mistakes

1. Ignoring $K_5$ or $K_{3,3}$ subgraphs: Always check for these as indicators of non-planarity.
2. Misapplying Euler's Formula: Ensure the graph is connected before using $v - e + f = 2$
3. Forgetting the Outer Face: Include the outer region as a face when applying Euler's formula.
4. Assuming all cycles are Hamiltonian: Not all graphs with cycles are Hamiltonian; verify carefully.
5. Overlooking graph redrawing: Non-planar graphs can sometimes be made planar with edge rearrangements.

Key Formulas and Concepts

1. Euler's Formula (Planar Graphs): $v - e + f = 2$

2. Kuratowski's Theorem:

• Non-planarity is caused by $K_5$ or $K_{3,3}$ subgraphs.

3. Hamiltonian Cycle: A cycle that visits every vertex once and returns to the start.