Graph Theory (Edexcel A-Level Further Mathematics): Revision Notes

Example 1: $K_n$Properties

Problem:

Find the number of edges in K7K_7 and the degree of each vertex.

Solution:

3. $n=7$
4. Number of Edges:

5. Degree of Each Vertex: Each vertex is connected to $7-1=6$ other vertices.

Answer: $K_7$ has 21 edges, and each vertex has degree 6.

Example 2: Planarity Check Using Euler's Formula

Problem:

A graph has 6 vertices, 10 edges, and 1 face. Is it planar?

Solution:

Using Euler's formula:

Substitute $v = 6, e = 10, f = 1$

The formula is not satisfied, so the graph is not planar.

Example 3: Testing for Isomorphism

Problem:

Check if the following graphs are isomorphic:

6. Graph A: Vertices $A, B, C, D$, edges $AB, AC, AD, BC$
7. Graph B: Vertices $W, X, Y, Z$, edges $WX, WY, WZ, XY$

Solution:

8. Number of Vertices: Both have 4 vertices.
9. Number of Edges: Both have 4 edges.
10. Degree Sequence:

• Graph A: $\{3, 2, 1, 1\}$
• Graph B: $\{3, 2, 1, 1\}$ Since all conditions match, the graphs are isomorphic.

Common Mistakes

1. Forgetting Euler's Formula: Always check for planarity with $v - e + f = 2$
2. Misinterpreting Isomorphism: Ensure degree sequences and edge connections match.
3. Counting Errors in KnK_n: Verify the formula $\frac{n(n-1)}{2}$
4. Assuming all graphs are planar: Some graphs like $K_5$ and $K_{3,3}$ are inherently non-planar.
5. Overlooking faces: Include the outer region when calculating $f$ in planar graphs.

Key Formulas

1. Edges in $K_n$:

2. Euler's Formula (Planar Graph):

3. Degree of Each Vertex in $K_n$: