Introduction to Graph Theory

Aug 24 2022

Graphs are the study of vertices and the edges “between” them. More formally, a simple graph or graph is a pair of sets $(\mathcal{V}, \mathcal{E})$ where $\mathcal{V}$ is any set and $\mathcal{E}$ is defined as any family of doubletons from $\mathcal{V}$ .

This introduction is mostly about (simple) graphs but will briefly cover other varieties of graphs for reference.

Types of Edges

There are a few popular forms of graphs, and they are studied based on what properties the edges take on:

Edges which are bidirectional are undirected.
Edges which are unidirectional are directed and may also be known as arrows.
Edges paired with numerical values are weighted.
Edges which are indexed are labeled.
Multiple edges between two vertices are arcs.
An edge which connects to the same vertex is a loop.

graph	arrow	loop	arc
graph	✗	✗	✗
multigraph	✗	✗	✓
loop graph	✗	✓	✗
loop multigraph	✗	✓	✓
digraph	✓	✗	✗
multidigraph	✓	✗	✓
loop digraph	✓	✓	✗
quiver	✓	✓	✓

There’s an unfortunate amount of disagreement on the precise meaning of these terms; some authors use multigraph and pseudograph interchangeably and others permit multigraphs with loops.

There are also hypergraphs where edges may connect more than two vertices at once.

A graph with fewer than $2$ vertices is trivial.
A graph with no vertices is the null graph.
A connected graph is one where there is a path between any two unique vertices.

Notation

Let $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ be a graph. Then for convenience we may refer to the vertex set of $\mathcal{G}$ as $V(\mathcal{G})$ and the edge set as $E(\mathcal{G})$ . For extra brevity one may also see $v ∈ \mathcal{G}$ for vertices and $e ∈ \mathcal{G}$ for edges.

Graphs

Let a graph be a pair of sets $(\mathcal{V}, \mathcal{E})$ with an incidence function $ϕ$ mapping primitive edges $\mathcal{E} = \{ e_i \}$ to a codomain that is a subset of $\mathcal{V}^2$ .

Terms

Diagonal Subset

This encodes for self-loops.

\Delta_\mathcal{V} := \{ (x, x) ∈ \mathcal{V}^2 \}

Quotient Set

This encodes for undirected edges.

\left\langle { \mathcal{V} \atop 2 } \right\rangle := \{ ( x, y ) ⊆ \mathcal{V}^2 \mid (x, y) = (y, x) \}

Quotient Set

This encodes a simple graph.

\left( {\mathcal{V} \atop 2} \right) := \{(x, y) ∈ \mathcal{V}^2 \mid (x, y) = (y, x) ∧ x ≠ y \, \}

Definitions

The incidence function $ϕ$ and its codomain determines the kind of graph.

graph	arrow	loop	arc	definition
graph	✗	✗	✗	$\mathcal{E} ↪ \left( \mathcal{V} \atop 2 \right)$
multigraph	✗	✗	✓	$\mathcal{E} → \left( \mathcal{V} \atop 2 \right)$
loop graph	✗	✓	✗	$\mathcal{E} ↪ \left\langle {\mathcal{V} \atop 2} \right\rangle$
loop multigraph	✗	✓	✓	$\mathcal{E} → \left\langle {\mathcal{V} \atop 2} \right\rangle$
digraph	✓	✗	✗	$\mathcal{E} ↪ \mathcal{V}^2 ∖ Δ_\mathcal{V}$
multidigraph	✓	✗	✓	$\mathcal{E} → \mathcal{V}^2 ∖ Δ_\mathcal{V}$
loop digraph	✓	✓	✗	$\mathcal{E} ↪ \mathcal{V}^2$
quiver	✓	✓	✓	$\mathcal{E} → \mathcal{V}^2$

Let $e_1, e_2$ be edges in a graph. If $ϕ(e_1) = ϕ(e_2)$ then they are parallel edges found in multigraphs. If the mapping is injective then there are no parallel edges.

Alternative Definition

Let $\mathcal{V}$ be a set of vertices. All of the following graphs may be defined as a pair of sets $(\mathcal{V}, \mathcal{E})$ where $\mathcal{E}$ takes on different properties. These graphs are notable for being easily represented by an adjacency matrix.

Graph

A simple graph or graph may be defined as a pair of sets $(\mathcal{V}, \mathcal{E})$ where $\mathcal{E}$ is any family of doubletons from $\mathcal{V}$ .

\mathcal{E} ⊆ \{ \{ x, y \} ⊆ \mathcal{V} \mid x ≠ y \, \}

Alternatively stated,

\mathcal{E} ⊆ \{ (x, y) ∈ \mathcal{V}^2 \mid (x, y) = (y, x) ∧ x ≠ y \, \}

Directed Graph

A directed graph or digraph may be identified:

\mathcal{E} ⊆ \{ (x, y) ∈ \mathcal{V}^2 \mid x ≠ y \, \}

Loop Graph

A loop graph may be identified:

\mathcal{E} ⊆ \{ ( x, y ) ⊆ \mathcal{V}^2 \mid (x, y) = (y, x) \}

Loop Digraph

A loop digraph may be identified:

\mathcal{E} ⊆ \mathcal{V}^2

Multigraph

A multigraph is a graph which permits parallel or multiple edges along any two distinct vertices. This may be represented in a variety of ways; for example we may have a multiplicity function $ϕ$ which given any edge will return the multiplicity of that edge.

Directed Multigraph

A directed multigraph is a multigraph with directed edges (also known as arcs or arrows).

Graph Traversal

A closed walk is one where the starting and ending vertex is the same.

A walk is an alternating sequence of vertices and edges.
A trail is a walk with no repeated edges.
A path is a trail with no repeated vertices.
A circuit is a closed trail.
A cycle is a closed path.
A Hamiltonian path is a path which visits all vertices in a graph. A Hamiltonian circuit is a Hamiltonian path which is closed.

term	repeat vertex	repeat edge	closed
walk	?	?	?
trail	?	✗	?
circuit	?	✗	✓
path	✗	✗	✗
cycle	✓	✗	✓

Subgraph

Let $\mathcal{G}_0 = (\mathcal{V}_0, \mathcal{E}_0)$ and $\mathcal{G}_1 = (\mathcal{V}_1, \mathcal{E}_1)$ be graphs. Then a subgraph relation $\mathcal{G}_0 ⊆ \mathcal{G}_1$ is defined:

\mathcal{G}_0 ⊆ \mathcal{G}_1 := (\mathcal{V}_0 ⊆ \mathcal{V}_1) ∧ (\mathcal{E}_0 ⊆ \mathcal{E}_1)

Spanning Subgraph and Supergraph

Let $\mathcal{G}_0 ⊆ \mathcal{G}_1$ . If $\mathcal{G}_0$ can become $\mathcal{G}_1$ by only removing edges then $\mathcal{G}_0$ is a spanning subgraph. Conversely, a spanning supergraph is a graph attained by only adding edges.

Induced Subgraph

Let $\mathcal{G}_0 = (\mathcal{V}_0, \mathcal{E}_0)$ be a subgraph of $\mathcal{G}_1 = (\mathcal{V}_1, \mathcal{E}_1)$ . A vertex induced subgraph is one where all possible edges are preserved from its supergraph.

\mathcal{G}[\mathcal{V}_0]

Let $\mathcal{E} = \{ e_i \}$ be a set of edges. An edge induced subgraph of $\mathcal{G}$ is one where for any subset of edges $\{ e_i \}$ we have all vertices incident to them. This may be denoted:

\mathcal{G}[\{ e_i \}]

Properties

Order

The order of a graph $\mathcal{G}$ is the cardinality of its vertex set, and is denoted $|\mathcal{G}|$ .

Size

The size of a graph $\mathcal{G}$ is the cardinality of the edge set, and is denoted $\|\mathcal{G}\|$ .

Adjacency

Two vertices within a graph are adjacent if there is an edge which joins them together.

Neighborhood

The set of all vertices adjacent to a vertex $v$ is called the open neighborhood of $v$ , denoted $N(v)$ . The closed neighborhood of $v$ is the open neighborhood but also including $v$ itself, denoted $N[v]$ .

Incidence

If an edge $e$ has a vertex $v$ , then $v$ is incident to $e$ . This may be denoted $v ∈ e$ .

Degree

Let $\mathcal{G}$ be a graph. The degree of a vertex $v ∈ \mathcal{G}$ is the cardinality of its open neighborhood, and is denoted $d(v)$ .

d(v) := |N(v)|

The minimum degree and maximum degree of $\mathcal{G}$ is also defined:

\delta (\mathcal{G}) := \min \, \{ d(v) : v ∈ \mathcal{G} \}

\Delta (\mathcal{G}) := \max \, \{ d(v) : v ∈ \mathcal{G} \}

When we use degree on a graph (as opposed to a vertex) we refer to its average degree.

d(\mathcal{G}) := \frac{1}{|\mathcal{V}|} \sum_{v ∈ \mathcal{V}} d(v)

As an observation we have:

\delta(\mathcal{G}) ≤ d(\mathcal{G}) ≤ \Delta(\mathcal{G})

Ratio of Edges to Vertices

The ratio of edges to vertices may be denoted:

ε(\mathcal{G}) := |\mathcal{E}| : |\mathcal{V}|

ε(\mathcal{G}) = \frac{1}{2} d(\mathcal{G})

|\mathcal{E}| = \frac{1}{2} d(\mathcal{G}) \times |\mathcal{V}|

Color

A graph coloring labels each vertex in a graph with a color such that no two adjacent vertices have the same color.

The chromatic number of a graph $\mathcal{G}$ is the minimal number of colors necessary in a graph coloring, denoted $χ(\mathcal{G})$ .

Independent

A set of vertices and edges are independent when no two elements are adjacent.

Union and Intersection

Let $\mathcal{G}_1 = (\mathcal{V}_1, \mathcal{E}_1)$ and $\mathcal{G}_2 = (\mathcal{V}_2, \mathcal{E}_2)$ be graphs. Then their union and intersection is defined:

\mathcal{G}_1 ∪ \mathcal{G}_2 := (\mathcal{V}_1 ∪ \mathcal{V}_2, \ \mathcal{E}_1 ∪ \mathcal{E}_2)

\mathcal{G}_1 ∩ \mathcal{G}_2 := (\mathcal{V}_1 ∩ \mathcal{V}_2, \ \mathcal{E}_1 ∩ \mathcal{E}_2)

Bipartite Graph

Let $\mathcal{G}$ be a graph and let $\mathcal{X}, \mathcal{Y}$ be a partition of the vertex set.

A bipartite graph is one where:

No two vertices in $\mathcal{X}$ are adjacent
No two vertices in $\mathcal{Y}$ are adjacent
All edges join some a vertex of $\mathcal{X}$ to a vertex of $\mathcal{Y}$ .

Complete Graph

Let $n$ be the number of vertices in a graph. Then a complete graph $K_n$ is one where all possible edges exist.

Size of $K_n$

Since any pair of vertices may potentially have an edge, finding the total number of possible edges between all pairs of vertices is the same as finding all $2$ -element subsets, and thus is an $n$ choose $2$ problem.

\begin{align} K_n = {n \choose 2} &= \frac{n!}{2!(n - 2)!} \\[0.8em] &= \frac{n(n-1)}{2} \end{align}

If we allow loops in our graph then the size of $K_n$ is:

{n + 1 \choose 2} = \frac{n(n + 1)}{2}

Tree

A forest is an acyclic graph and a (free) tree is a connected forest.

A rooted tree is a tree with a vertex (or node) labeled as the root.

Resources

nLab

Introduction to Graph Theory

Types of Edges

Notation

Graphs

Terms

Diagonal Subset

Quotient Set

Quotient Set

Definitions

Alternative Definition

Graph

Directed Graph

Loop Graph

Loop Digraph

Multigraph

Directed Multigraph

Graph Traversal

Subgraph

Spanning Subgraph and Supergraph

Induced Subgraph

Properties

Order

Size

Adjacency

Neighborhood

Incidence

Degree

Ratio of Edges to Vertices

Color

Independent

Union and Intersection

Bipartite Graph

Complete Graph

Size of KnK_nKn​

Tree

Resources

Size of $K_n$