Graphs

Graphs are mathematical objects consisting of nodes and edges. The original inventor of graph theory was Leonhard Euler, who used it to solve the Seven Bridges of Königsberg problem.

Notes

Diestel - Graph Theory

Link: http://www.cs.unibo.it/babaoglu/courses/cas00-01/tutorials/GraphTheory.pdf

Chapter 1: Basics

Outline:

• Definitions (graph, degree, path, cycle, connectivity, tree, forest, k-partite, contraction, Euler tours)

Graph definitions

A graph G consist of a set of nodes (vertices) V and edges E, denoted $ G(V,E) $

Vertex set on graph G is denoted $ V(G) $

Edge set on graph G is denoted $ E(G) $

Number of vertices in a graph is called the order and is denoted $ |G| $

Number of edges in a graph is denoted $ ||G|| $

Vertex $ v \in V $ and edge $ e \in E $ are incident if the edge connects to the vertex.

Set of all edges at a particular vertex v is denoted $ E(v) $

Two vertices x, y are adjacent on a graph if there is an edge with endpoints x and y

If all vertices are pairwise adjacent, the graph is complete

For two graphs $ G = (V,E) $ and $ G' = (V',E') $, the graphs are isomorphic if there exists a biijection from G to G'.

If we have two graphs G and G', we say that G' is a subgraph of G if all V' subset of V and all E' subset of E

A subgraph G' is a spanning subgraph of G if all V' span all of G (if V' = V)

Degree definitions

Set of neighbors of a vertex v is denoted $ N(v) $

Degree of a vertex v is denoted $ d(v) $ and is equal to the number of edges $ |E(v)| $ at v

Vertex of degree 0 is isolated

The vertex on the graph with the smallest degree $ \delta(G) = \min \left( d(v) | v \in V \right) $ is the minimum degree of G

The vertex on the graph with the largest degree $ \Delta(G) = \max \left( d(v) | v \in V \right) $ is the maximum degree of G

The average degree of G is given by the expression $ d(G) = \dfrac{1}{|V|} \sum_{v \in V} d(v) $

Ratio of edges to vertices on a graph is $ \epsilon(G) = \dfrac{|E|}{|V|} $

If we define edges as having two endpoints, then adding up the degrees of all vertices will lead to twice the number of edges. Mathematically: $ |E| = \dfrac{1}{2} \sum_{v \in V} d(v) = \dfrac{1}{2} d(G) |V| $

This leads to the identity $ \epsilon(G) = \dfrac{1}{2} d(G) $ and the theorem that the number of vertices of odd degree in a graph must always be even. Contrawise proof: if the number of vertices of odd degree is odd, the number of edges is not be an integer.

Path and Cycle Definitions

A path P on a graph G is a non-empty graph that contains vertices and edges that are in G: $ V = \{ x_1, x_2, \dots, x_k\} $ and $ E = \{ x_0 x_1, x_1 x_2, \dots, x_{k-1} x_k \} $

A path is usually referred to by the sequence of vertices it visits, or as a path "from/between x1 to xk"

Independent paths are paths containing no common (internal) vertices. Independent paths may share endpoints though.

We can denote parts of a path using special notation: if a path $ P = x_0 \dots x_{k} $, then the following notation is used to denote only a part of that path:

$ \begin{align} P x_i = x_0 \dots x_i \qquad 0 \leq i \leq k \\ x_i P = x_i \dots x_k \\ x_i P x_j = x_i \dots x_j \end{align} $

We can also connect paths using unions, or by using more shorthand:

$ P x \bigcup x Q y \bigcup y R = P x Q y R $

A cycle C consists of a path whose final edge connects the last node to the first node. Given a path $ P = x_0 \dots x_{k-1} $ the cycle is then $ C = P + x_{k-1} x_0 $

A k-cycle is denoted $ C^k $ and is a cycle of length k.

Chapter 2: Matching

Bipartite graph matching

k-partite graph matching

Chapter 3: Connectivity

2-connected graphs

3-connected graphs

Menger's Theorem

Mader's Theorem

Spanning trees (and edge-disjoint spanning trees)

Chapter 4: Planar Graphs

Topology

Plane graphs

Algebraic criteria

Chapter 5: Coloring

Coloring vertices

Coloring edges

Chapter 6: Flows

Circulations

Flows in networks

k-flows

Flow coloring

Tutte's flow conjectures

Chapter 7 and 8: Substructures

Subgraphs

Regularity lemma

Hadwigen's theorem