Midterm 2 Graph Theory Thms/Facts

Cayley’s formula

n^{n-2}

Two things are true if G is eulerian

• every vertex of G has even degree

• edges can be partitioned into edge-disjoint cycles

If e lies ___________, then G is Eulerian

on an odd number of cycles

With G order n>= 3, if δ(G) _____, then G is hamiltonian

>= n/2

K_{n,m} is traceable iff

|n - m| <= 1

K_{n,m} is hamiltonian iff

n = m
for n,m >= 2

Let G be a graph order n >= 3. If __________ for all pairs of nonadj. vertices x,y, then G is __________.

deg(x) + deg(y) >= n, Hamiltonian

Let G be connected order n >= 3 with vertex connectivity k(G) and independence number α(G). If _______, then G is __________

k(G) >= α(G), hamiltonian

Every _____ is planar

tree

If e is a bridge of a planar graph G, then

e does not bound a region in any planar rep of G

For a connected graph that is not a tree, every region in a planar rep of G is bounded by

a cycle

What is lower bound on the bounding number b(R) of any region

b(R) >= 3

If G is planar graph with n>= 3 vertices and q edges, then q _______. If q _______ , then every region is bounded by three edges

<= 3n - 6, = 3n - 6

Lower bound of sum of all bounding numbers of G

3r

Sum of all bounding numbers of G is always equal to

2q

If G is a planar graph, then δ(G)

<= 5

For all polyhedra, __ <= ρ <= __

3, 5

Odd cycles are not ____ - colorable, but even cycles are

2

If G is a graph w/ k connected comp. G1,..., Gk, then Χ(G) =

max{X(G_i)} for i <= k

For a complete multipartite graph K_{n1, ….. ns}, Χ(K_{n1, ….. ns}) =

s

Adding an edge to G increases its chromatic number by

at most one

Only graph of order n w/ Χ(G) = n is

K_n

Let τ(G) be number of vertices in longest path in G, then

Χ(G) <= τ(G)

For any graph G, Χ(G) _____, where Δ(G) is the maximum degree of G

<= Δ(G) + 1,

Brooks Thm: ______ for all connected graphs except a complete graph or an odd cycles

Χ(G) <= Δ(G)

for any graph _____ ω(G)

Χ(G) >=