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

Example 1: Determine the Type of Graph

Problem:

Given the graph:

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

Solution:

1. Find Orders of Vertices:

• $A = 2, B = 3, C = 3, D = 2$

2. Count Odd Orders:

• Odd: $B,C$ (2 vertices).

3. Classify the Graph:

• Two odd-order vertices → Semi-Eulerian.

Example 2: Check if a Graph is Eulerian

Problem:

Given the graph:

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

Solution:

4. Find Orders of Vertices:

• $A = 2, B = 2, C = 2, D = 2$

5. Count Odd Orders:

• Odd: None.

6. Classify the Graph:

• All even-order vertices → Eulerian.

Example 3: Neither Eulerian nor Semi-Eulerian

Problem:

Given the graph:

• Vertices: $A, B, C, D$
• Edges: $AB, AC, BD$

Solution:

7. Find Orders of Vertices:

• $A = 2, B = 2, C = 1, D = 1$

8. Count Odd Orders:

• Odd: $C, D$ (2 vertices).

9. Connectedness Check:

• Graph is disconnected (no path between $C$ and $D$).

10. Classify the Graph:

• Disconnected → Neither.

Common Mistakes

1. Miscounting Orders: Ensure each vertex's degree includes all connected edges.
2. Ignoring Connectedness: A graph must be connected to be Eulerian or semi-Eulerian.
3. Confusion About Odd Vertices: Semi-Eulerian graphs must have exactly two odd-order vertices.
4. Overlooking Special Cases: Loops (edges connecting a vertex to itself) contribute 2 to the vertex's order.
5. Assuming All Cycles are Eulerian: Only cycles with even-order vertices are Eulerian.

Key Formulas and Rules

1. Eulerian Graph:

• All vertices have even order.
• The graph is connected.

2. Semi-Eulerian Graph:

• Exactly two vertices have an odd order.
• The graph is connected.

3. Neither:

• More than two odd-order vertices or the graph is disconnected.