Planar Graphs Flashcards
What is Euler’s formula for connected plane pseudographs?
n-m+f=2
What is the 4-colour Theorem
Every map is 4-colourable
For every plane graph with n \geq 3 vertices what is the most amount of edges it can contain?
3n-6 edges
Every plane graph has a vertex of degree of at most?
5
What is Whitney’s Theorem for 3-connected planar graphs?
every 3-connected planar graph has a unique plane embedding
What is Steinitz’s Theorem for when a graph is polyhedral.
If and only if it is planar and 3-connected.
What is Chvatal’s Theorem for the Art Gallery problem?
Every polygon P with n vertices can be guarded by at most the floor of n/3 guards.
Every embedding of a ___ ___ graph with at least 3 vertices is a ___ ____
Every embedding of a maximal planar graph with at least 3 vertices is a plane triangulation.
Every n-vertex planar graph G is ___-colourable
5
What is Kuratowski’s Theorem?
A graph G is planar iff G contains no subdivision of K_5 or K_{3,3} as a subgraph.