Graph Theory Final Review

Question 1

Kuratowski’s Theorem (Minors)

Answer 1

A Graph G is not planar iff it has a K3,3 or K5 minor

Question 2

Kuratowski’s Theorem (Topological Minors)

Answer 2

A Graph G is not planar iff it has a topological minor isomorphic to K3,3 or K5

Question 3

Menger’s Theorem (Disjoint s-t paths)

Answer 3

Let S and T be sets of vertices in a graph G then for k element of integers one of the following is true 1) There exist k disjoint s-t paths or 2) There is a k-1 separation (A,B) of G with s within A and t within B

Question 4

Menger’s Theorem (Internally disjoint s-t paths)

Answer 4

Let S and T be distinct non adjacent vertices in a graph G then for k where k is an element of the integers one of the following statements is true either 1) There exist k internally disjoint s-t paths or 2) There is a k-1 separation of (A,B) of G with S element of V(A)\V(B) and T element of V(B)\V(A)

Question 5

K connected

Answer 5

If G - X is connected for all sets x element of V(G) and |x| < k

Question 6

Block

Answer 6

Maximal nonseperable subgraph

Question 7

3 Facts about Blocks

Answer 7

1) A Graph G is planar iff all its blocks are planar
2) A Graph G is bipartite iff all its blocks are bipartite
3) A Graph G is k-colorable iff all its blocks are k-colorable

Question 8

What is the number of ears in a loopless 2 connected graph?

Answer 8

|E|-|V|+1

Question 9

What properties do the excluded minors of planar graphs have

Answer 9

Simple and 3 connected

Question 10

Tuttle’s Wheel Theorem

Answer 10

Let G be a simple 3 connected graph with |V(G)| >= 4. If G is not a wheel then there exists an edge in G such that either G-e or G/e is both simple and 3 connected

Question 11

Prove Kuratowski’s Theorem for Minors using Tuttle’s Wheel theorem

Answer 11

Page 21-23

Question 12

Theorem [Tuttle]

Answer 12

Let C be a cycle in a graph G then G is planar iff for each bridge B of C the graph B U C is planar and the overlap graph is bipartite.

Question 13

What condition causes a graph G to have a separating cycle and what opposite condition causes a graph G to be planar

Answer 13

If |E| > |V| + 1 then G has a seperating cycle. If |E| <= |V| + 1 G is planar

Question 14

Tutte’s matching theorem

Answer 14

A graph G has no perfect matching iff there exists vertices of G named X such that odd(G-X) > |X|

Question 15

2 Tuttle Berge formulas

Answer 15

Max matching = Min(|X|+(|V(G-X)|- odd(G-X))/2) For all possible X subset of V(G)

Def(G) = Max odd(G-x)-|X|

Question 16

Edmond Gallai Theorem

Answer 16

T(G) is a Tuttle Set

Question 17

Edmond’s Matching Algorithm

Answer 17

IDK