1
Sum of Degrees Theorem
The sum of the degrees of all vertices is twice the number of edges:
$$\sum d(v) = 2E$$
Crucial Corollary: The sum of degrees $\sum d(v)$ must ALWAYS be an even number!
2
Loops and Multiple Edges
In non-simple graphs:
- Loop (Gelung): An edge that connects a vertex to itself. Contributes 2 to the degree of that vertex!
- Multiple Edges (Berbilang tepi): Two or more edges connecting the same pair of vertices.
3
Properties of a Tree (Pokok)
A tree is a connected simple graph that has:
$$E = V - 1$$
- No loops, no multiple edges.
- No closed circuits/cycles.
- Every pair of vertices is connected by exactly one path.
SPM Question Trap: Can a graph be drawn with given degrees?
If an SPM question gives a set of degrees such as $(2, 3, 2, 4, 1)$:
1. Calculate sum $\sum d(v) = 2 + 3 + 2 + 4 + 1 = 12$ (even number $\checkmark$).
2. Check if the number of odd-degree vertices is even. Here, odd degrees are 3 and 1 (2 odd vertices $\checkmark$).
If $\sum d(v)$ is odd, state: "No, because the sum of degrees $\sum d(v)$ is not an even number."