Graphs

To begin, what's a graph? A graph is a pair of countable sets $(V,E)$, where

• $V$ is a countable set of singleton elements called vertices,
• $E$ is a subset of the set of all unordered pairs $\{\{v_1,v_2\}\ \vert\ v_1,v_2 \in V, v_1\not= v_2\}$. The elements of $E$ are called edges.

A graph is drawn by simply connecting points representing vertices together by a line segment if they belong to the same edge. A digraph, or directed graph, is a pair of countable sets $(V,E)$, where

• $V$ is a countable set of vertices,
• $E$ is a subset of ordered pairs $\{(v_1,v_2)\ \vert\ v_1,v_2 \in V, v_1\not= v_2\}$ called edges.

A digraph is drawn by simply connecting points representing vertices together by an arrow if they belong to the same edge $(v_1,v_2)$, the arrow originating at $v_1$ and arrowhead pointing to $v_2$. If $e=\{v_1,v_2\}$ belongs to $E$ then we say that $e$ is an ``edge from $v_1$ to $v_2$'' (or from $v_2$ to $v_1$). If $v$ and $w$ are vertices, a path from $v$ to $w$ is a finite sequence of edges beginning at $v$ and ending at $w$:

$$e_0=\{v,v_1\}, e_1=\{v_1,v_2\}, ..., e_n=\{v_n,w\}.$$

If there is a path from $v$ to $w$ then we say $v$ is connected to $w$. We say that a graph $(V,E)$ is connected if each pair of vertices is connected. The number of edges eminating from a vertex $v$ is called the degree (or valence) of $v$, denoted ${\rm degree}(v)$.

Example 5.15.1   : If

$$V = \{a,b,c\},\ \ \ \ E=\{\{a,b\},\{a,c\},\{b,c\}\},$$

then we may visualize $(V,E)$ as

Each vertex has valence 2.

Definition 5.15.2   : If $v$ and $w$ are vertices connected to each other in a graph $(V,E)$ then we define the distance from $v$ to $w$, denoted $d(v,w)$, by

$$d(v,w) = \min_{v,w\in V \ {\rm connected}} \char93 \{ {\rm edges\ in\ a\ path\ from\ }v\ {\rm to\ }w\}$$

By convention, if $v$ and $w$ are not connected then we set $d(v,w) =\infty$. The diameter of a graph is the largest possible distance:

$${\rm diam}((V,E)) = \max_{v,w\in V} d(v,w).$$

In the above example, the diameter is 1.