Graph Theory

A simple graph is a pair (V,E) where V is set (of nodes) and E is a set of 2-elementary subsets of V, which are called edges. General graphs are allowed to have multiple edges between a pair of nodes or loops, that is, edges from a node to itself.

The simple graphs are precisely the 1-dimensional abstract simplicial complexes.

A directed graph (also called digraph) has arcs instead of edges, where an arc is an ordered pair of nodes.

Typically, our graphs are finite.


  1. Norman Biggs: Algebraic Graph Theory, 2nd ed. Cambridge Mathematical Library. Cambridge University Press (1994).
  2. Bela Bollobas: Modern Graph Theory, Graduate Texts in Mathematics 184. New York, Springer (1998).
  3. Douglas B. West: Introduction to Graph Theory, Upper Saddle River, NJ: Prentice Hall (1996).