Graph Theory final

A graph is a tree iff

Every 2 vertices are connected by a unique path

How many leaves does every tree have

At least 2

Equation for the edges in a tree

||T|| = |T| - 1

Every connected graph has a

Spanning tree

A graph is bipartite iff (2 things)

2 colorable, no odd cycles

A graph if Eurlerian iff

It is connected and even

Veblem’s theorem, TFAE:

1. G is even

2. All components of G are Eulerian

3. There exists a family of circuits C so that every edge of G is in exactly one circuit in C

4. There exists a family of cycles C so that every edge of G is in exactly one circuit in C

Dirac’s

(Let G have order n>=3) G is Hamiltonian if for every vertex v of G we have deg(v)>=n/2

Ore’s

(Let G have order n>=2) G is Hamiltonian if for every pair of vertices v, w of G we have deg(v)+ deg(w) >= n

A graph is Hamiltonian iff

Its closure is Hamiltonian

If the closure if a graph is complete then

The original graph is Hamitonian

Chvatal: If graph G of order n>=3 has degree sequence d1<=…<=dn satisfying…

satisfying, for all k<n/2, if dk<=k then d(n-k)>=n-k, then G is Hamiltonian

If G is connected then G³ is

Hamiltonian-connected

Degree equivalense is

2-switch equivalence

A block-cut graph is a

Tree

A graph is 2-edge connected if and only if it has

Closed ear decomposition

A graph is 2-connected if and only if it has

Open ear decomposition

Every 3-connected graph as an edge e such that

G/e (the edge contraction) is 3-conencted

Menger’s vertex/set

The maximum size of a collection of pairwise disjoint A-B paths is equal to the minimum size of an A-B separating set

Menger’s vertex/vertex

The maximum size of a collection of pairwise internally disjoint u-v paths is equal to the minimum size of a set separating u and v

Menger’s Vertex/Global

A graph with at least k+1 vertices is k-connected if and only if for every pair of distinct vertices u and v, there is a collection of k internally disjoint u-v paths.

Menger’s Edge/Vertex

The maximum size of a collection of pairwise edge-disjoint u-v paths is equal to the minimum size of a u-v edge separating set

Menger’s edge/global

A graph G is L-egde connected iff for all distinct vertices u, v there are L edge disjoint u-v paths in G

Whitney’s inequalities

kappa(G) <= lambda(G) <= delta(G)

Konig-Egervary

The maximum size of a matching in (bipartite) G equals the minimum size of a vertex cover

Hall’s Marriage Theorem

• A (bipartite) graphg G has a matching of U with a subset of W iff for every S subset of U we have |S|<=|N(S)|

• A graph G has a perfect matching iff |U|=|W| and for every S subset of U |S|<=|N(S)|

Chvatal & Erdos

kappa(G) > alpha(G) → Hamiltonian

Euler’s Polyhedral Formula

V-E+F=2

Euler’s identity

n-m+r=2

G is planar and n>=3 then": (bound for edges)

m<=3n-6

Every planar graph contains a vertex

of degree 5 or less

A graph is Kuratovski if

It is a subdivision of K^3,3 or K⁵

G is outerplanar iff (2 things)

It has no subdivision of K^2,3 or K⁴ OR iff G * K² is planar

Upper bound for chrmatic number

chromatic number <= |G| - alpha(G) + 1

Lower bound for chromatic number

clique number <= chromatic number

Upper bound for chromatic number (less simple)

chromatic number <= ½ + sqrt(2||G|| + 1/4)

Vizing (an upper bound on chromatic number)

chromatic number <= max degree + 1

If G is an interval graph then the chromatic number

Chromatic number equal the clique number

Lower bound for chromatic number (with alpha)

|G| / alpha(G) <= chromatic number

There are two classes of graph with resepct to edge coloring:

• Edge chromatic number = max degree

• Edge chromatic number = max degree + 1

Tait (statement…)

Every planar, 3-regular, bridgeless graph is 3-edge colorable

What is a snark

A planar, 3-regular, bridgeless graph that is NOT 3-edge colorable