Planar Graphs

Question 1

What is Euler’s formula for connected plane pseudographs?

Answer 1

n-m+f=2

Question 2

What is the 4-colour Theorem

Answer 2

Every map is 4-colourable

Question 3

For every plane graph with n \geq 3 vertices what is the most amount of edges it can contain?

Answer 3

3n-6 edges

Question 4

Every plane graph has a vertex of degree of at most?

Answer 4

5

Question 5

What is Whitney’s Theorem for 3-connected planar graphs?

Answer 5

every 3-connected planar graph has a unique plane embedding

Question 6

What is Steinitz’s Theorem for when a graph is polyhedral.

Answer 6

If and only if it is planar and 3-connected.

Question 7

What is Chvatal’s Theorem for the Art Gallery problem?

Answer 7

Every polygon P with n vertices can be guarded by at most the floor of n/3 guards.

Question 8

Every embedding of a ___ ___ graph with at least 3 vertices is a ___ ____

Answer 8

Every embedding of a maximal planar graph with at least 3 vertices is a plane triangulation.

Question 9

Every n-vertex planar graph G is ___-colourable

Answer 9

5

Question 9

What is Kuratowski’s Theorem?

Answer 9

A graph G is planar iff G contains no subdivision of K_5 or K_{3,3} as a subgraph.