SME
Discrete Mathematics
Graph theory
Use this for “A connected planar graph has 6 vertices and 9 edges. How many faces?”
Diagram
Each degree is written beside its vertex; they add to 18 = 2 × 9, since every edge has two ends.
V − E + F = 2: 6 − 9 + 5 = 2, counting the outer face.
This is an example. Type your own values to start a new problem.
V
−
E
+
F
=
2
Σ deg
=
2
×
E
d̄
Average degree
calculated
Formulas
Σ
deg
=
2
×
E
18 = 2 × 9
d̄
=
Σ deg
V
3
=
18
6
V
−
E
+
F
=
2
6 − 9 + 5 = 2
Assumptions
•
The graph is simple (no loops or repeated edges), connected and drawn with no edges crossing.
•
Each edge has two ends, so it adds 1 to the degree of each of two vertices.
•
Faces are the regions the drawing cuts the plane into, the outer, unbounded one included.
•
For V ≥ 3, a simple planar graph has at most 3V − 6 edges.
Step-by-step
WE KNOW
V = 6, E = 9
FIND
degree sum (Σ deg), average degree (d̄), faces (F)
Step 1 · Find degree sum (Σ deg)
Use Σ deg = 2 × E
Handshake lemma: each edge has two ends, so it counts once in each of two degrees.
Σ deg = 2 × 9
Σ deg = 18
Step 2 · Find average degree (d̄)
Use d̄ = (Σ deg) ÷ V
The degree sum shared over the vertices.
d̄
=
18
6
d̄
=
3
Step 3 · Find faces (F)
Use V − E + F = 2
Euler’s formula for a connected planar graph, solved for the faces.
F
=
2
−
V
+
E
F
=
2
−
6
+
9
F
=
5
Check
Put the numbers back in. Both sides should match.
18 = 2 × 9 ✓
3
=
18
6
✓
6 − 9 + 5 = 2 ✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.
More problem types
Trees and full m-ary trees
Use this for “A full 3-ary tree has 4 internal vertices. How many vertices, leaves and edges?”
Edges of complete graphs
Use this for “How many edges has K₇? How many has the complete bipartite graph K₃,₄?”
Euler circuit, Euler path or neither
Use this for “A connected graph has degrees 3, 3, 2, 2. Does it have an Euler path or an Euler circuit?”