Graph Theory Exam 3

Front 1

chi'(G) for Peterson graph

Back 1

4

Front 2

chi'(G) for even cycle

Back 2

2

Front 3

chi'(G) for odd cycle

Back 3

3

Front 4

chi'(G) for K_n

Back 4

n

Front 5

chi'(G) for bipartite

Back 5

2

Front 6

chi'(G) for star

Back 6

2

Front 7

Konig: If G is bipartite(multi-graph), then

Back 7

chi'(G) = maxdeg(G)

Front 8

(Vizing) If G is simple then chi'(G) is

Back 8

maxdeg(G) or maxdeg(G) + 1

Front 9

For multi-graph, chi'(G) is

Back 9

<= 3maxdeg/2

Front 10

Konig proof (multi,bipartite) chi'(G) = maxdegree

Back 10

it suffices to show chi'(g) <= maxdeg.

a) For k-regular graphs, use induction on k and Corollary 3.1.8 to Hall's Theorem.

b) Then show G of the theorem is a subgraph of a maxdeg(G)-regular bipartite graph.

full proof:

a) by corallary to hall's, G has a perfect matching M. Color all edges in M with color k. If k = 1, this is a 1-edge coloring of G. Otherwise, G-M is a k-1 regular bipartite graph. If we assume inductively that k-1-reg bipartite graphs have a k-1 edge coloring, this gives a k-edge coloring of G.

b) If G is not regular, let k = maxdeg(G). Show G is a subgraph of a k-reg bipartite graph H. By (a) H has a proper k-edge coloring therefore so does G. To construct H from G, add verts to make X and Y even. Then, connect edges until regular.

Front 11

Corallary to Hall's Theorem:

Back 11

Every k-regular bipartite graph with k > 0 has a perfect matching

Front 12

Deciding whether graph is max or max + 1 edge-colorable

Back 12

NP-complete

Front 13

Hamiltonian cycle(path)

Back 13

spanning cycle(path) in G.

Front 14

G is Hamiltonian if G has a

Back 14

Hamiltonian cycle

Front 15

G is vertex transitive if for any vertices in V there is an isomorphism f: G -> G such that f(v) = V

Back 15

examples: K_n, C_n, Q_k, Petersen, Kn,n

Front 16

Q_k

Back 16

hamiltonian

Front 17

Circumference of G

Back 17

length of longest cycle

if = n(g) then Hamiltonian

Front 18

time solvable? hamiltonian cycle, path, circumference

Back 18

no polynomial-time algorithms NP-hard

Front 19

Necessary: If G is Hamilton, then has property

Sufficient: if has property, is hamiltonian

Back 19

x

Front 20

Necessary: If G is Hamiltonian, then for any S contained in V,

Back 20

G-S has at most |S| components.

Front 21

Sufficent: (Dirac) If G is simple and n(G) >=3 and

Back 21

mindeg(G) >= n(G)/2, then G is Hamiltonian. Proof - counterexample

Front 22

Necessary and sufficient: (Bondy-Chvatal) G is Hamiltonian iff

Back 22

the closure of G is Hamiltonian

Front 23

Closure

Back 23

Take graph, G. Add edges between vertices whose degrees adds up to n(G). Repeat until can't any longer.

Front 24

Sufficient: (Chvatal) Suppose G has degree sequence(d1,...,dn)(increasing where d1<= d2<=...dn.

Back 24

If i < n/2 implies that either di > i or dn-i >= n -1, then G is Hamiltonian.

Front 25

(Ore) If G is simple and u and v are non-adjacent vertices with d(u) + d(v) >= n(G),

Back 25

then G is Hamiltonian iff G+uv is Hamiltonian.

Front 26

Travelling Salesman problem

Back 26

Given weighted K_n (non neg), find minimum weight Hamiltonian cycle (no poly time solution known). If the triangle inequality holds for all vertices, possible to find good approximation

Front 27

the number of edges in L(G) is

Back 27

sum of (d(v)/2) for all v in G

Front 28

G is isomorhpic to L(G) iff

Back 28

G is 2-reg

Front 29

If G is Eulerian

Back 29

L(G) is Hamiltonian

Front 30

There are non-eulerian graphs whose

Back 30

L(G) are Hamiltonian

Front 31

For which pairs (n, k) is J(n, k) claw free? Answer:

Back 31

if and only if k < 3 or n < k + 3.

Front 32

A2[i, j]

MMT[i, j]

Back 32

A2 [i, j] = This counts the number of paths of length 2 from i to j.MMT [i, j] This is counting the number of edges joining i and j, so for a simple graph, MMT [i, j] = A[i, j].

Front 33

Matrix multiplication

Front 34

Matrix tree thm

Front 35

Dijstra's

Front 36

Kruskal's

Front 37

Circumference, girth, eccentricity, diameter, radius

Back 37

circumference - longest cycle

girth - shortest cycle

radius - smallest eccentricity

diameter - largest eccentricity

eccentricity: furthest distance from any other vertex(shortest path to furthest away)

Front 38

n-ribbed fan graph Gn,

Back 38

τ (Gn) = τ (Gn−1) + τ (Hn−1) and τ (Hn) = τ (Gn) + τ (Hn−1), where Hn is the graph obtained from Gn by “doubling” the first rib

Front 39

Spanning trees of petersen graph?

Back 39

2000

Front 40

Dijstra's fails in prescence of negative weights

Back 40

adding -m doesn't work because it distorts paths with more edges than other paths.

Front 41

If you find a flow that matches a src/sink cut

Back 41

then it must be max flow and min capacity since

f <= cap

Front 42

Euler's formula

Back 42

n-e+f = 2

Front 43

Every simple planar graph G has a vertex of degree

Back 43

at most 5. Use 3n-6 to show that couldn't have min degree higher.

Front 44

Which n,r pairs in Turan is it planar?

Back 44

r>=5 doesn't work. r =1 works, r=2 and n<=5, r=3 and n<=6, r=4 and n<=5

Front 45

thickness of a graph

Back 45

how many planar graphs do you have to decompose nonplanar to get all planar

Front 46

Brook's theorem outline

Back 46

look at it