Planar Graphs Flashcards

1
Q

What is Euler’s formula for connected plane pseudographs?

A

n-m+f=2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is the 4-colour Theorem

A

Every map is 4-colourable

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A

3n-6 edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

A

5

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A

every 3-connected planar graph has a unique plane embedding

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Every n-vertex planar graph G is ___-colourable

A

5

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is Kuratowski’s Theorem?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly