The vocabulary of networks. Every other Networks topic, Euler paths, minimum spanning trees, shortest path, uses these ideas. Get the basics right and everything else clicks into place.
What even is this?
A graph is a collection of dots (vertices) connected by lines (edges). That's literally it. They're used to model road networks, social connections, project schedules, power grids, anything where things connect to other things.
This page gives you the key terms and rules you need before anything else in Networks makes sense. Learn these first.
4 words unlock this whole page
Vertexa dot in the network
Degreehow many edges touch a vertex
Edgea line connecting two vertices
Weighta number on an edge (distance, cost, time)
Everything else on this page (digraph, tree, handshaking lemma...) is just these four ideas
combined or named differently. If those four stick, the rest follows.
1
Vertices and Edges
Vertex (pl. vertices)
A point or node in the graph. Drawn as a dot, usually labelled with a letter.
Real world: towns, computers, junctions, people
Edge
A line connecting two vertices. Represents a connection or relationship between them.
Real world: roads, cables, friendships, pipelines
Edges: A, B, A, C, B, C, B, D, C, D | Degree labels in gold
2
Degree of a Vertex
The degree of a vertex is the number of edges connected to it. Count the lines attached to each dot.
Vertex
Connected to
Degree
A
B, C
2
B
A, C, D
3
C
A, B, D
3
D
B, C
2
Total (sum of all degrees)
10
Handshaking Lemma
Sum of all degrees = 2 × (number of edges)
Why? Every edge connects exactly two vertices, so each edge contributes exactly 2 to the total degree sum. If the graph has e edges, the sum of degrees = 2e.
In our example: 2 + 3 + 3 + 2 = 10 = 2 × 5 ✓
Odd and even degrees matter. The number of vertices with odd degree determines whether a graph is traversable (this comes up in Euler Paths, next topic).
3
Types of Graphs
Simple Graph
No loops (edge from a vertex to itself) and no parallel edges (two edges between the same pair). The default type.
Used for: most network problems in this course
Directed Graph (Digraph)
Edges have arrows, you can only travel in the direction shown. A→B does not mean you can go B→A.
Used for: one-way streets, activity networks, workflows
Weighted Graph
Each edge has a number (weight) showing distance, time or cost. Most practical graph problems use weights.
Used for: MST, shortest path, critical path analysis
Connected Graph
Every vertex can be reached from every other, the graph is in one piece. A disconnected graph has isolated clusters.
Required for: spanning trees, Euler circuits
4
Trees
A tree is a connected graph with no cycles. It's the most efficient way to connect all nodes, no redundant connections.
Tree Formula
A tree with n vertices has exactly n − 1 edges
Why n − 1? Start with 1 vertex and 0 edges. Each time you add a new vertex, you connect it with exactly 1 new edge (to keep it connected without creating a cycle). After adding n − 1 more vertices you have n vertices and n − 1 edges.
A tree with 6 vertices must have exactly 5 edges, and no cycles
5
Worked Examples
📐
Example A · Degrees and the Handshaking Lemma
A graph has vertices P, Q, R, S, T with edges PQ, PR, QR, QS, RS, ST. Find the degree of each vertex and verify the handshaking lemma.
1
Count edges at each vertex
P connects to: Q, R → degree 2
Q connects to: P, R, S → degree 3
R connects to: P, Q, S → degree 3
S connects to: Q, R, T → degree 3
T connects to: S → degree 1
2
Verify the lemma
Sum of degrees = 2 + 3 + 3 + 3 + 1 = 12
Number of edges = 6 → 2 × 6 = 12 ✓
Which type of graph should you use to model a one-way road network? Explain why.
Tap to reveal ▾
A directed graph (digraph), because the arrows show which direction travel is allowed. In an undirected graph, every edge can be used in both directions, but one-way roads can only be used in one direction.
5
A network has 7 vertices. Every vertex has the same degree and the sum of all degrees is 28. What is the degree of each vertex, and how many edges are in the network?
Tap to reveal ▾
Each vertex degree = 28 ÷ 7 = 4
Number of edges = 28 ÷ 2 = 14 edges