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

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