To begin, what's a graph? A graph is a pair of countable sets , where
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
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 .
then we may visualize as
Each vertex has valence 2.
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.