Graph Theory Exam 2

planar graph

a graph that can be drawn without crossings

plane graph

a plane drawing of a planar graph

A graph is planar if and only if it contains no subgraph homeomorphic to K5 or K3,3

Kuratowski’s theorem

contractible to K5 or K3,3

we can obtain K5 or K3,3 by contracting edges

crossing number of G (cr(G))

the minimum number of crossings that can occur when G is drawn in the plane

faces

If G is a planar graph, then any plane drawing of G divides the set of points of the plane not lying on G into regions called ____

Euler’s formula

formula that tells us that whatever plane drawing of a planar graph we take, the number of faces is always the same

n-m+f=2

Euler’s formula: Let G be a plane drawing of a connected planar graph, and let n be the number of vertices, m the number of edges, and f the number of faces. Then…

n-m+f=k+1

Euler’s formula can be applied to disconnected graphs: Let G be a plane graph with n vertices, m edges, f faces, and k components. Then…

5

Every simple planar graph contains a vertex of degree at most _

thickness of G (t(G))

the smallest number of planar graphs that can be superimposed to form a graph G

k-colorable

For a graph G without loops, we can assign one of k colors to each vertex so that adjacent vertices have different colors

k-chromatic

If G is k-colorable but not (k-1)-colorable, G is _______

chromatic number of G

If G is k-chromatic, then k is the _____

n

chromatic number of Kₙ

G is (D+1)-colorable

If G is a simple graph with largest vertex degree D, then…

every simple planar graph is 4-colorable

four color theorem

map

3-connected plane graph

cutsets with 1 or 2 edges or vertices of degree 1 or 2

a map contains no…

k-colorable(f)

a map whose faces can be colored with k colors so that no two faces with a boundary edge in common have the same color

G is an Eulerian graph

a map G is 2-colorable(f) if and only if…

A necessary and sufficient condition for a solution of the matching problem is that each set of k girls collectively knows at least k boys (for 1 <= k <= m with m total girls)

Hall’s theorem

the maximum number of edge-disjoint paths connecting two distinct vertices v and w of a connected graph is equal to the minimum number of edges in a vw-disconnecting set

Menger’s theorem

edge-disjoint paths

paths from v to w that have no edge in common

vertex-disjoint paths

paths from v to w that have no vertex in common (except v and w)

vw-disconnecting set

a set E of edges of G such that each path from v to w includes an edge of E

vw-separating set

a set of S vertices (other than v and w) such that each path from v to w passes through a vertex of S