Appendix E
Groups and Graphs
Definition of graphs.
Definition E.1. A graph X consists of a vertex set V = V(X) and an
edge set E = E(X), equipped with two maps s, r: E--+ V, called the source
map and the range map (s(e) is the vertex at which an edge begins, while
r(e) is the vertex at which it ends). A simple graph is a graph without
loops or multiple edges, i.e., s(e) i= r(e) for every e E E and the map
E 3 e 1--+ ( s( e), r( e)) E V^2 is injective. When dealing with a simple graph,
we identify the edge e with ( s ( e), r ( e)) E V^2. A simple graph is undirected
if (x, y) EE implies (y, x) EE.
Except for those used in graph C* -algebras, all graphs are assumed to
be simple and undirected. We say two vertices x, y E V are adjacent if
(x, y) EE. We often identify the graph X with its vertex set V. A path a
of length n (possibly n = oo) in X is a sequence xox1 · · · Xn of vertices such
that Xk+l is adjacent to Xk for every 0:::; k < n. We say the path a connects
xo to Xn. It's convenient to assume the graph Xis connected: For any pair
of vertices, there exists a path which connects one to the other. The (graph)
metric on the vertex set V is
d(x, y) = min{n: :la path of length n which connects x toy}.
A path xox1 · · · is called a geodesic if d(xn, Xm) = Jn - m[ for all n, m.
Lemma E.2. Let a = xox1 · · · be an infinite geodesic path in X and y E X
be a vertex. Then, there is a geodesic path /3 = YoY1 · · · starting at y = Yo and
which eventually flows into a, i.e., there exists k E Z such that Yn = Xk+n
for all large enough n.
- 471