Euler's formula for planar graphs

Euler's formula for planar graphs Flashcards

Spec DA3 · AQA A-Level Further Maths: Flashcards

Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.

13 cards

Tap a card to flip it. Swipe right if you knew it, left if not.

See all 13 cards
State Euler's formula for a connected planar graph.
v−e+f=2v-e+f=2
What does ff include in Euler's formula?
All faces, including the outer (unbounded) face.
What is a planar graph?
A graph that can be drawn in the plane with no edges crossing.
A connected planar graph has v=8v=8, e=12e=12. Find ff.
f=2−8+12=6f=2-8+12=6
How many faces does a tree have?
One, the outer face; for a tree e=v−1e=v-1.
Effect on ff of adding a new vertex joined by one edge?
None; vv and ee both increase by 11.
Effect on ff of adding an edge between two existing vertices (no crossings)?
ff increases by 11.
Effect on ff of subdividing an edge?
None; one vertex and one edge are added.
What is the sum of the face degrees?
2e2e, because each edge borders two faces (or the same face twice).
If every face has degree 33, which equation links ee and ff?
3f=2e3f=2e
Why does a simple planar graph have 2e≥3f2e\ge3f?
Every face has at least 33 edges, as there are no loops or multiple edges.
Rearrange Euler's formula for ee.
e=v+f−2e=v+f-2
Why must the graph be connected?
Euler's formula v−e+f=2v-e+f=2 applies to connected graphs; disconnected graphs have a different constant.

Flashcards