Graphs, An Introduction


A graph is a set of vertices V, and a set of edges E that connect pairs of points in V.  Edges are actually determined by a symmetric irreflexive relation on V cross V.  Some graphs may include loops (a point connected to itself) or multiple edges (many lines connecting a pair of points), but they are the exceptions.  Unless otherwise indicated, the term "graph" refers to the definition above.

A digraph contains vertices and edges as above, but the edges are directed.  In other words, the edge relation need not be symmetric.  The edge v1→v2 does not imply the edge v2→v1.  Edges are drawn using arrows, rather than line segments.  Again, loops and multiple edges are usually prohibited.

A vertex has degree n if there are n edges connecting that vertex to other vertices.  The number of edges is half the sum of the degrees.

In a digraph, vertices have indegrees and outdegrees.  The number of directed edges is the sum of the indegrees, or the sum of the outdegrees.