Graph theory studies networks — points (vertices) joined by lines (edges). It models roads, circuits and social connections.
1. Vertices, edges and degree
- A vertex (node) is a point; an edge is a line joining two vertices.
- The degree of a vertex is the number of edges meeting at it.
Handshake rule
$\text{sum of all degrees} = 2 \times (\text{number of edges})$Every edge adds one to the degree of each of its two ends — so the degrees always add up to twice the number of edges.
Worked example
A network has $5$ edges. What is the sum of the degrees of all its vertices?
Sum of degrees $= 2 \times 5 = 10$.
Exam tips
- The degree of a vertex = the number of edges touching it.
- Sum of all degrees $= 2 \times$ number of edges (every edge is counted twice).
- A network can be directed (arrows) or undirected; weighted edges carry a value.