Graph Theory

Degree

Definitions

Regular Graph

If a graph in which every vertex has degree k, for some fixed k, is called a k-regular graph (or a regular graph)

Theorems

Handshaking Lemma (Degree-Sum Formula)

\underset{v \in V(G)}{\Sigma} deg(v) = 2|E(G)|

The average degree of a vertex in the graph G

\frac{2|E(G)|}{|V(G)|}

Corollary

The number of vertices of odd degree in a graph is even.

Bipartite Graphs

Definitions

Bipartite

A graph in which the vertices can be partitioned into two sets A and B, so that all edges join a vertex in A to a vertex in B, is called a bipartite graph, with bipartition (A, B).

Lemma

•

An odd cycle is not bipartite

Theorem

•

A graph is bipartite if and only if it has no odd cycles

Paths and Cycle

•

If every vertex in G has degree at least 2, then G contains a cycle

Bridges

•

An edge e is a bridge of a graph G if and only if it is not contained in any cycle of G 

•

If there are two distinct paths from vertex u to vertex v in G, then G contains a cycle.

Tree

Definitions

Tree

A tree is a connected graph with no cycles

Lemma

•

Every edge of a tree T is a bridge

•

If T is a tree, then ∣E(T)∣=∣V(T)∣−1|E(T)| = |V(T)| - 1∣E(T)∣=∣V(T)∣−1

Spanning Trees

•

A graph G is connected if and only if it has a spanning tree.

•

If G is connected with p vertices and q = p -1 edges, then G is a tree

•

If T is a spanning tree of G and e is an edge not in T, then T + e contains exactly one cycle C. Moreover, if e’ is any edge on C, then T + e - e’ is also a spanning tree.

•

If T is a spanning tree of G and e is an edge in T, then T - e has 2 components. If e’ is in the cut induced by one of the components, then T - e + e’ is also a spanning tree of G.

Bipartite Graphs Character

•

An odd cycle is not bipartite 

•

A graph is bipartite if and only if it has no odd cycles.

Planar Graphs

Definition

Planar

A graph G is planar if it has a a drawing in the plan so that its edges intersect only at their ends, and so that no two verticies coincide.

Faces

A planar embedding partitions the plan into connected regions called faces.

Theorems

Handshaking Lemma for Faces (Faceshaking Lemma)

If we have a planar embedding of a connected graph G with faces

f_1,...,f_n

, then

\overset{s}{\underset{i=1}{\Sigma}} deg(f_i) = 2|E(G)|

Corollary

If the connected graph G has a planar embedding with f faces, the average degree of a face in the embedding is

\frac{2|E(G)|}{f}

Euler’s Formula

Let G be a connected graph with p verticies and q edges. If G has a planar embedding with f faces, then

p - q + f = 2

Nonplanar Graphs

Lemma

•

If G contains a cycle then in a planar embedding of G, the boundary of each face contains a cycle

•

Let G be a planar embedding with p vertices and q edges. If each face of G has degree at least d*, then (d∗−2)q≤d∗(p−2)(d^* - 2)q \le d^*(p-2)(d∗−2)q≤d∗(p−2)

Theorems

•

In a planar graph G with p ≥ 3 vertices and q edges, we have q ≤ 3p-6

•

A planar graph has a vertex of degree at most five

•

In a bipartite planar graph G with p ≥ 3 vertices and q edges, we have q ≥ 2p - 4

Tree

If u and v are verticies in a tree T, then there is a unique u,v-path in T

Every edge of a tree T is a bridge

If T is a tree, then

|E(T)| = |V(T)|-1

Kuratowski’s Theorem

A graph is not planar if and only if it has a subgraph that is an edge subdivision of K_5 or K_3,3

Konig’s Theorem

Hall’s Theorem

A bipartite graph G with bipartition A,B has a matching saturating every vertex in A, if and only if every subset D of A satisfies

|N(D)|\ge|D|