## Graphs

To begin, what's a graph? A graph is a pair of countable sets , where

• is a countable set of singleton elements called vertices,

• is a subset of the set of all unordered pairs . The elements of 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 , where

• is a countable set of vertices,

• is a subset of ordered pairs called edges.

A digraph is drawn by simply connecting points representing vertices together by an arrow if they belong to the same edge , the arrow originating at and arrowhead pointing to .

If belongs to then we say that is an edge from to '' (or from to ). If and are vertices, a path from to is a finite sequence of edges beginning at and ending at :

If there is a path from to then we say is connected to . We say that a graph is connected if each pair of vertices is connected. The number of edges eminating from a vertex is called the degree (or valence) of , denoted .

Example 5.16.1   : If

then we may visualize as

Each vertex has valence 2.

Definition 5.16.2   : If and are vertices connected to each other in a graph then we define the distance from to , denoted , by

By convention, if and are not connected then we set . The diameter of a graph is the largest possible distance:

In the above example, the diameter is 1.

david joyner 2008-04-20