Graphs

Definition: Graph

A graph \((V, E)\) consists of a set \(V\) and a collection \(E\) of unordered pairs of elements of \(V\):

  • The elements of \(V\) are called vertices or nodes;
  • The elements of \(E\) are called edges or branches. Each edge \(e \in E\) is a set \(\{u, v\}\) of two distinct vertices \(u, v \in V\).

For \(e = \{u, v\} \in E\):

  • We say that \(u\) and \(v\) are adjacent or neighbors.
  • We say that \(e\) is incident to \(u\) and \(v\).

Definition: Subgraph

Let \(G = (V, E)\) be an undirected graph.

A subgraph of \(G\) is an undirected graph \(G' = (V', E')\) with the following properties:

  • \(V' \subseteq V\);
  • \(E' \subseteq E\).

Definition: Walk

A walk in an undirected graph \(G = (V, E)\) is an alternating sequence

\[ (v_0, e_1, v_1, e_2, v_2, \dotsc, e_k, v_k) \]

of vertices and edges such that \(e_i = \{v_{i-1}, v_i\}\) for all \(1 \le i \le k\).

Definition: Length

We call \(k \in \mathbb{N}_0\) the length of the walk.

Definition: Path

A path is a walk

\[ (v_0, e_1, v_1, e_2, v_2, \dotsc, e_k, v_k) \]

such that \(v_i \ne v_j\) for all distinct \(i, j \in \{0, \dotsc, k\}\).

Definition: Connectedness

An undirected graph is connected if for every pair of distinct vertices \(u\) and \(v\) there exists a path between \(u\) and \(v\).