Basic Concepts of Graph Theory

The definitions here mainly follow Prof. Grinberg’s Graph Theory course in UMN.

Some of the notation and definitions come from Diestel’s book.

If \(S\) is a set, then the powerset of \(S\) means the set of all subsets of \(S\). This powerset will be denoted by \(\mathcal P (S)\). For example, the powerset of \(\{1, 2\}\) is \(\mathcal P(\{1, 2\}) = \{\emptyset, \{1\} , \{2\} , \{1, 2\}\}\).

Furthermore, if \(S\) is a set and \(k\) is an integer, then \(\mathcal P_k (S)\) shall mean the set of all \(k\)-element subsets of \(S\). (This is empty if \(k < 0\).)

Graph

Definition: A simple graph is a pair \((V, E)\), where \(V\) is a finite set, and where \(E\) is a subset of \(\mathcal P_2(V)\).

Digraph

Directed Acyclic Graph, DAG

Bipartite Graph

Definition: A bipartite graph, also called a bigraph, is a set of graph vertices decomposed into two disjoint sets such that no two graph vertices within the same set are adjacent. A bipartite graph is a special case of a \(k\)-partite graph with \(k=2\).

Hamiltonian Path (Cycle)

Definition: A Hamiltonian path is a path that visits each vertex of the graph exactly once. 

Note that determining whether Hamiltonian paths and cycles exist in graphs is the Hamiltonian path problem, which is NP-complete.

Eulerian Tour

Definition: A closed walk in a graph is called an Euler tour if it traverses every edge of the graph exactly once. A graph is Eulerian if it admits an Euler tour.

Matching

A set \(M\) of independent edges in a graph \(G =(V,E)\) is called a matching. \(M\) is a matching of \(U \sube V\) if every vertex in \(U\) is incident with an edge in \(M\). The vertices in \(U\) are then called matched (by \(M\)); vertices not incident with any edge of \(M\) are unmatched.

Colouring

Definition: A vertex colouring of a graph \(G =(V,E)\) is a map \(c: V\to S\) such that \(c(v) \ne c(w)\) whenever \(v\) and \(w\) are adjacent. The elements of the set \(S\) are called the available colours.

Flow