Euler's formula for planar graphs 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.
- What does 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 , . Find .
- How many faces does a tree have?
- One, the outer face; for a tree .
- Effect on of adding a new vertex joined by one edge?
- None; and both increase by .
- Effect on of adding an edge between two existing vertices (no crossings)?
- increases by .
- Effect on of subdividing an edge?
- None; one vertex and one edge are added.
- What is the sum of the face degrees?
- , because each edge borders two faces (or the same face twice).
- If every face has degree , which equation links and ?
- Why does a simple planar graph have ?
- Every face has at least edges, as there are no loops or multiple edges.
- Rearrange Euler's formula for .
- Why must the graph be connected?
- Euler's formula applies to connected graphs; disconnected graphs have a different constant.