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.16.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.16.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.