1550075568-C-Algebras_and_Finite-Dimensional_Approximations__Brown_

472 E. Groups and Graphs

Proof. Form, n with m ~ n, we define h(m, n) = d(y, xm) + d(xm, xn) -

d(y, xn)· Note that h decreases (resp. increases) as m (resp. n) increases and

that h(m, k) = h(m, n) + h(n, k) for every m ~ n ~ k. Since 0 ~ h(m, n) ~

2d(y, xo), h(m) = limk h(m, k) exists. We note that h(m) = h(m, n) + h(n)

for every m ~ n. It follows that for mo such that h(mo) =inf h(m), we have

h(mo, n) = 0 for every n ~ mo. Therefore, letting /3 be the concatenation

of a geodesic path connecting y to Xmo and the subpath Xm 0 Xmo+l · · • of a,

we are done. D

Definition E.3. A (simple and connected) graph Xis called a tree if there

is no nontrivial loop, i.e., there is no path xox1 · · · Xn such that Xn = xo,

n > 2, and x1, ... , Xn are all distinct.

Example E.4. Let r be a group and S be a set of generators such that

e tJ_ S. Then, the Cayley graph X = X(r, S) of r with respect to S is

the graph whose vertex set is r and whose edge set is E = {(s, t) : s-^1 t E

SU s-^1 }. For example, if r = JF 2 is freely generated by S = {a, b }, then the

corresponding Cayley graph is a tree (of degree four).

b

ab

a-l e a a2

ab-^1

b-1

Figure 1. The Cayley graph of 1F2

The group of automorphisms on X (i.e., isometric bijections on V) is
denoted by Aut(X). An action of a group r on the graph X is a group
homomorphism from r into Aut(X). The action is said to be (metrically)
proper if for every F CV of finite diameter, the set f{s Er: sF n F # 0}[
is finite. The stabilizer of a vertex x E V is the subgroup

rx = {s EI': s.x = x} CI'.