Duplicate

# Graph Theory

Category
Course Notes
Parent item
Sub-category
MATH
Sub-item
Tags
Graph Theory
MATH 239
Combinatorics

## 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$

## 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 \le 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|$