Graph

Overview

A directed graph $G$ is a pair $⟨ V, E ⟩$ , where $V$ is a finite set and $E$ is a binary relation on $V$ . An undirected graph $G$ is a pair $⟨ V, E ⟩$ , where $V$ is a finite set and $E$ is a set of unordered pair of vertices from $V$ . In both types of graphs, $V$ is called the vertex set of $G$ and $E$ is called the edge set of $G$ .

Incidence

If $⟨ u, v ⟩$ is an edge of a directed graph, we say $⟨ u, v ⟩$ is incident to $v$ and incident from $u$ . Furthermore, we say $v$ is adjacent to $u$ . If ${u, v}$ was instead an edge of an undirected graph, we say ${u, v}$ is incident on $u$ and $v$ . Likewise, $v$ is adjacent to $u$ and $u$ is adjacent to $v$ .

Handshake Lemma

In any graph, the sum of the degrees of vertices in the graph is always twice the number of edges:

\sum_{v \in V} d (v) = 2 e .

Completeness

A complete graph is an undirected graph in which each vertex is connected to every other vertex. The complete graph on $n$ vertices is denoted by $K_{n}$ .

Likewise, a complete digraph is a digraph in which every distinct ordered pair of vertices is connected by a unique edge.

Subgraphs

We say $G^{'} = ⟨ V^{'}, E^{'} ⟩$ is a subgraph of $G = ⟨ V, E ⟩$ provided $V^{'} \subseteq V$ and $E^{'} \subseteq E$ . We say $G^{'} = ⟨ V^{'}, E^{'} ⟩$ is an induced subgraph of $G = ⟨ V, E ⟩$ provided $V^{'} \subseteq V$ and every edge in $E$ whose vertices are still in $V^{'}$ is also an edge in $E^{'}$ .

Cliques

A clique of undirected graph $G$ is a complete induced subgraph of $G$ . In other words, it is a subset of $G$ such that every two distinct vertices in the clique are adjacent.

A $k$ -clique is a clique that contains $k$ nodes.

Multigraphs

A graph that allows multiple edges between vertices is called a multigraph. It is analogous to the concept of multisets in set theory.

Walks

Let $G = (V, E)$ be a graph. A walk of $G$ is a sequence of vertices such that consecutive vertices in the sequence are adjacent in $G$ . More precisely, a walk (of length $k$ ) from vertex $v_{0}$ to vertex $v_{k}$ is a sequence $w = ⟨ v_{0}, v_{1}, \dots, v_{k} ⟩$ of vertices such that $(v_{i - 1}, v_{i}) \in E$ for $i = 1, 2, \dots, k$ .

We say $v_{k}$ is reachable from $v_{0}$ via $w$ . We denote reachability of $v_{k}$ from $v_{0}$ as $v_{0} ⇝ v_{k}$ .

Trails

A trail is a walk in which no edge is repeated.

Paths

A path is a trail in which no vertex is repeated (except possibly the first repeated as the last). A cycle is a path that starts and ends at the same vertex. A graph with no cycles is acyclic.

In computer science, a cycle is sometimes required to have more than one edge:

In a directed graph, path $⟨ v_{0}, v_{1}, \dots, v_{k} ⟩$ is a cycle if $v_{0} = v_{k}$ and the path contains at least one edge.
In an undirected graph, path $⟨ v_{0}, v_{1}, \dots, v_{k} ⟩$ is a cycle if $v_{0} = v_{k}$ and all edges are distinct.

Hamiltonian Path

A Hamiltonian path is a path that visits every vertex in the graph exactly once (except possibly the first repeated as the last). A Hamiltonian cycle is a Hamiltonian path that starts and ends on the same vertex.

Transpose

Let $G = ⟨ V, E ⟩$ be a directed graph. We define the transpose of $G$ as $G^{T} = ⟨ V, E^{T} ⟩$ where

E^{T} = {⟨ v, u ⟩ ∣ ⟨ u, v ⟩ \in E} .

Components

An undirected graph is connected if every two vertices are reachable from one another. The connected components of an undirected graph are the equivalence classes under the "is mutually reachable" relation.

A directed graph is strongly connected if every two vertices are reachable from one another. The strongly connected components of a digraph are the equivalence classes under the "is mutually reachable" relation.

A directed graph is weakly connected if for every two vertices, one is reachable from the other. In other words, a directed graph is weakly connected if its corresponding undirected graph is connected.

Cuts

Let $G = ⟨ V, E ⟩$ be an undirected graph. A cut ${S, V - S}$ of $G$ is a partition of $V$ . We say an edge ${u, v}$ crosses the cut ${S, V - S}$ if one of its endpoints belongs to $S$ and the other belongs to $V - S$ . A cut respects a set $A$ of edges if no edge in $A$ crosses the cut. An edge is a light edge crossing a cut if its weight is the minimum of any edge crossing the cut.

Isomorphisms

An isomorphism between two graphs $G_{1}$ and $G_{2}$ is a bijection $f : V_{1} \to V_{2}$ between the vertices of the graphs such that $(a, b)$ is an edge in $G_{1}$ if and only if $(f (a), f (b))$ is an edge in $G_{2}$ . Here parenthesis are used to denote either ordered pairs (for directed graphs) or unordered pairs (for undirected graphs).

We say $G_{1}$ and $G_{2}$ are isomorphic, denoted $G_{1} ≃ G_{2}$ , if and only if there exists an isomorphism between $G_{1}$ and $G_{2}$ .