**Graph C*-Algebras**

Introduction

A directed graph is the simplest combinatorial object that carries a topological dynamics: its vertices are the states, its edges the transitions, and its finite paths the orbits. The $\mathrm{C}^*$-algebra of a directed graph is obtained by reading the graph as a set of relations among partial isometries: one projection for each vertex, one partial isometry for each edge, with the edge isometry running between the two vertex projections and the projections of the edges leaving a vertex summing to the vertex projection. The resulting algebra $C^*(E)$ is the graph $\mathrm{C}^*$-algebra of $E$, also called the Cuntz–Krieger algebra of $E$ in honour of the two algebras from which the construction grew: the Cuntz algebras $\mathcal{O}_n$, generated by $n$ isometries with orthogonal ranges, and the Krieger algebras of topological Markov chains. The construction is a strictly topological one: it uses no measure, no dynamics beyond a graph, and no analysis; it is the $\mathrm{C}^*$-algebraic counterpart of a free construction, and its subject is the relation between the combinatorics of the graph and the ideal structure, the simplicity and the invariants of the algebra.

The theory is unusually complete. A graph $\mathrm{C}^*$-algebra is separable and nuclear; it carries a canonical gauge action of the circle group, and the fixed-point algebra of that action — the core — is an AF algebra built from the finite paths of the graph. The gauge-invariant ideals correspond to the saturated hereditary subsets of the vertices, simplicity is decided by two combinatorial conditions (cofinality and the exit condition on cycles), and the injectivity of a $*$-homomorphism out of $C^*(E)$ is decided by its behaviour on the vertex projections, either under a gauge-equivariance hypothesis or under the exit condition. The algebra is therefore a case in which the whole structure theory is read off from a finite or countable combinatorial datum, and it is the standard test case for the general theory of this category: crossed products, groupoid algebras, K-theory and KK-theory all receive their first examples here.

This article develops directed graphs and Cuntz–Krieger families, the existence and universal property of $C^*(E)$, the spanning theorem, the gauge action and the core, the gauge-invariant and Cuntz–Krieger uniqueness theorems, the classification of ideals and the simplicity criterion, and the fundamental examples: the one-loop graph with $C(\mathbb{T})$, the Toeplitz algebra as the associated Toeplitz–Pimsner algebra, the Cuntz algebras $\mathcal{O}_n$ and $\mathcal{O}_\infty$, and the finite acyclic graphs with their finite-dimensional algebras. Throughout, $E$ is a countable directed graph, $E^0$ its vertex set, $E^1$ its edge set, $r,s: E^1 \to E^0$ the range and source maps, and $E^*$ the set of finite paths; a row-finite graph is one in which every vertex emits at most finitely many edges, and the sums in the Cuntz–Krieger relations are then finite. Hilbert spaces are denoted $H$, operators on them $B(H)$, the compact operators $K(H)$, and the $\mathrm{C}^*$-algebras are those of Operator Algebras; the topology of the spectrum and the gauge action is the topology of the circle group, and the crossed-product and groupoid formalisms, the $K$-theory of the algebras constructed here and the extension theory of their Toeplitz extensions are treated in this Part. The analysis of the dynamics associated with a graph — the measures, the invariant integration and the $L^p$ theory of the path space — belongs to Part III.

Directed Graphs and Cuntz–Krieger Families

Graphs

Definition. A directed graph $E = (E^0, E^1, r, s)$ consists of a set of vertices $E^0$, a set of edges $E^1$, and maps $r, s : E^1 \to E^0$ assigning to each edge $e$ its range $r(e)$ and its source $s(e)$. The graph is countable if $E^0$ and $E^1$ are countable and row-finite if $s^{-1}(v)$ is finite for every $v \in E^0$. A vertex $v$ is a sink if it emits no edges, $s^{-1}(v) = \emptyset$, and a source if it receives no edges, $r^{-1}(v) = \emptyset$.

Definition. A finite path of length $k \geq 1$ is a sequence $\mu = e_1e_2\cdots e_k$ of edges with $r(e_i) = s(e_{i+1})$ for $1 \leq i \leq k-1$; its source and range are $s(\mu) = s(e_1)$ and $r(\mu) = r(e_k)$. The vertices are the paths of length $0$, with $s(v) = r(v) = v$. The set of finite paths is denoted $E^*$ and the set of paths of length $k$ by $E^k$. A cycle is a path $\mu$ of length $\geq1$ with $s(\mu) = r(\mu)$; a cycle has an exit if some vertex on it emits an edge not belonging to the cycle, and the graph satisfies condition (L) if every cycle has an exit.

Definition. A subset $H \subseteq E^0$ is hereditary if $s(e) \in H$ implies $r(e) \in H$ for every edge $e$, and saturated if whenever $v$ is not a sink and $r(e) \in H$ for every $e$ with $s(e) = v$, then $v \in H$. The graph is cofinal if for every vertex $v$ and every infinite path $x = e_1e_2\cdots$ there is an index $n \geq 0$ together with a finite path from $v$ to the vertex $r(e_n)$, so that every vertex can reach every tail of the graph.

The Cuntz–Krieger Relations

Definition. Let $E$ be a row-finite graph. A Cuntz–Krieger $E$-family in a $\mathrm{C}^*$-algebra $B$ consists of projections $\{p_v : v \in E^0\}$ and partial isometries $\{s_e : e \in E^1\}$ in $B$ satisfying

$$ \text{(K1)}\quad p_vp_w = \delta_{vw}p_v , \qquad \text{(K2)}\quad s_e^*s_f = \delta_{ef}p_{r(e)} , \qquad \text{(K3)}\quad s_es_e^* \leq p_{s(e)} , \qquad \text{(K4)}\quad p_v = \sum_{s(e)=v}s_es_e^* \ \ \text{whenever } s^{-1}(v) \neq \emptyset . $$

The relation (K2) says that the partial isometries have mutually orthogonal initial projections, all equal to $p_{r(e)}$ in the case $e = f$; (K3) says that the image of $s_e$ lies in the subspace $p_{s(e)}H$; (K4) is the Cuntz–Krieger relation, which says that the images of the edge isometries leaving $v$ exhaust the vertex projection $p_v$. For a non-row-finite graph the sum in (K4) is interpreted as a strictly convergent sum in the multiplier algebra, and the theory extends to that case; the present article works with row-finite graphs and records the extensions.

Proposition (consequences of the relations). For a Cuntz–Krieger $E$-family:

(a) $p_{s(e)}s_e = s_e = s_ep_{r(e)}$ for every edge $e$;

(b) for a finite path $\mu = e_1\cdots e_k$ the product $s_\mu = s_{e_1}\cdots s_{e_k}$ is a partial isometry with

$$ s_\mu^*s_\mu = p_{r(\mu)} , \qquad s_\mu s_\mu^* \leq p_{s(\mu)} ; $$

(c) if $\mu,\nu$ are finite paths with $r(\mu) \neq r(\nu)$ then $s_\mu^*s_\nu = 0$; and if $r(\mu) = r(\nu)$ and $\lvert\mu\rvert = \lvert\nu\rvert$ then $s_\mu^*s_\nu = \delta_{\mu\nu}p_{r(\mu)}$. For paths of different lengths the product need not vanish: if $ef$ is a path with $r(e) = r(f)$ then $s_e^*s_{ef} = s_f \neq 0$.

Proof. (a) is (K2) with $e=f$ together with (K3) written as $p_{s(e)}s_es_e^* = s_es_e^*$, giving $p_{s(e)}s_e = p_{s(e)}s_es_e^*s_e = s_es_e^*s_e = s_e$ and similarly on the right. (b) follows by induction from (a) and (K2), the induction step being $s_{\mu e}^*s_{\mu e} = s_e^*s_\mu^*s_\mu s_e = s_e^*p_{r(\mu)}s_e = s_e^*s_e = p_{r(e)}$, which is $p_{r(\mu e)}$. For (c), $s_\mu^* = p_{r(\mu)}s_\mu^*$ and $s_\nu = s_\nu p_{r(\nu)}$ by (a), so the product is $p_{r(\mu)}(s_\mu^*s_\nu)p_{r(\nu)}$ and vanishes when the two vertex projections are orthogonal; when the lengths agree and $r(\mu) = r(\nu)$, induction on the length using (K2) gives $s_\mu^*s_\nu = \delta_{\mu\nu}p_{r(\mu)}$. For the final example, $s_e^*s_{ef} = s_e^*s_es_f = p_{r(e)}s_f = s_f$ using (a) and $r(e) = s(f)$.

Definition. The graph $\mathrm{C}^*$-algebra $C^*(E)$ is the universal $\mathrm{C}^*$-algebra generated by a Cuntz–Krieger $E$-family: there is a Cuntz–Krieger $E$-family $\{p_v, s_e\}$ in $C^*(E)$ — the generating family — such that for every Cuntz–Krieger $E$-family $\{q_v, t_e\}$ in a $\mathrm{C}^*$-algebra $B$ there is a unique $*$-homomorphism

$$ \phi : C^*(E) \longrightarrow B , \qquad \phi(p_v) = q_v , \quad \phi(s_e) = t_e . $$

Theorem (existence and uniqueness). For every countable row-finite graph $E$ the universal algebra $C^*(E)$ exists, is unique up to a unique isomorphism, and is separable; the generating family generates $C^*(E)$ as a $\mathrm{C}^*$-algebra, and every element of $C^*(E)$ is a norm limit of finite linear combinations of the monomials $s_\mu s_\nu^*$ with $\mu,\nu \in E^*$.

Proof. The free $*$-algebra on the symbols $\{p_v, s_e\}$ carries the ideal generated by the Cuntz–Krieger relations, and the quotient by its closure in the universal representation of the free algebra is the algebra required; the construction is the standard one for a universal $\mathrm{C}^*$-algebra given by polynomial relations, and it produces a Cuntz–Krieger family satisfying the universal property by construction. Separability follows from the countability of $E^0$ and $E^1$ and the density of the polynomial span of the monomials. Alternatively, the regular representation of the family on $\ell^2(E^\infty)$ — the path space of the graph — realises $C^*(E)$ concretely, and the two descriptions agree by universality. This is the standard construction; it is quoted as standard.

The Structure of a Graph C*-Algebra

The Spanning Theorem

Theorem (spanning). For every countable row-finite graph $E$,

$$ C^*(E) = \overline{\operatorname{span}}\bigl\{s_\mu s_\nu^* : \mu, \nu \in E^*,\ r(\mu) = r(\nu)\bigr\} . $$

Proof. The right-hand side is closed under multiplication and under the involution by the relations (c) above together with the Cuntz–Krieger relation: a product $s_\mu s_\nu^* s_\alpha s_\beta^*$ is zero unless the range conditions are compatible, and otherwise reduces to a monomial $s_{\mu'}s_{\beta'}^*$ with $r(\mu') = r(\beta')$; the Cuntz–Krieger relation rewrites a vertex projection as a sum of monomials with paths one step longer, which is what keeps the span closed. Since the span is a $\mathrm{C}^*$-algebra containing the generating family, it equals $C^*(E)$ by the universal property; the details are standard and are quoted.

Example (verification of the spanning theorem). For the graph with two vertices $v,w$ and one edge $e$ with $s(e) = v$, $r(e) = w$, the algebra is realised by the matrices

$$ p_v = \begin{pmatrix}1&0\\0&0\end{pmatrix}, \quad p_w = \begin{pmatrix}0&0\\0&1\end{pmatrix}, \quad s_e = \begin{pmatrix}0&1\\0&0\end{pmatrix}, $$

and the Cuntz–Krieger relations hold exactly: $s_e^*s_e = p_w$, $s_es_e^* = p_v$, $p_v + p_w = 1$. The monomials $s_\mu s_\nu^*$ with $r(\mu) = r(\nu)$ here are $p_v$, $p_w$, $s_e$ and $s_e^*$, and these four matrices have rank $4$ in the four-dimensional space $M_2(\mathbb{C})$; so $C^*(E) \cong M_2(\mathbb{C})$. For the path $v_1 \to v_2 \to v_3$ with edges $e_1,e_2$, the matrices $s_{e_1} = E_{12}$, $s_{e_2} = E_{23}$ and $p_{v_i} = E_{ii}$ satisfy the relations $s_{e_1}^*s_{e_1} = p_{v_2}$, $s_{e_2}^*s_{e_2} = p_{v_3}$, $s_{e_1}s_{e_1}^* = p_{v_1}$, $s_{e_2}s_{e_2}^* = p_{v_2}$, and the $14$ monomials $s_\mu s_\nu^*$ with $r(\mu) = r(\nu)$ span a space of rank $9$, which is all of $M_3(\mathbb{C})$; the redundant monomials are exactly the linear dependencies among the matrix units.

The Gauge Action and the Core

Theorem (gauge action). Let $E$ be a countable row-finite graph. There is a strongly continuous action of the circle group

$$ \gamma : \mathbb{T} \to \operatorname{Aut}C^*(E) , \qquad \gamma_z(p_v) = p_v , \qquad \gamma_z(s_e) = z\,s_e , $$

the gauge action, and it is determined uniquely by these formulas. Its fixed-point algebra

$$ C^*(E)^\gamma = \{x \in C^*(E) : \gamma_z(x) = x \ \text{for all } z \in \mathbb{T}\} $$

is the closed span of the monomials $s_\mu s_\nu^*$ with $\lvert\mu\rvert = \lvert\nu\rvert$, and it is an AF algebra, the core of $C^*(E)$.

Proof. The formulas define a Cuntz–Krieger family for each $z$, namely $\{p_v, zs_e\}$, since each relation is homogeneous in the edge isometries; universality therefore produces $\gamma_z$, and multiplicativity in $z$ and continuity follow from the uniqueness clause of the universal property. The span of the gauge-invariant monomials is closed and is precisely the fixed-point algebra by the standard Fourier argument on the circle action. That the core is AF for a row-finite graph is the theorem of Kumjian–Pask: the finite-dimensional subalgebras generated by the monomials supported on paths of length at most $n$ form an increasing sequence with dense union. It is quoted as standard.

Remark. The gauge action is the circular symmetry of the graph algebra and the reason the theory splits into a combinatorial part (the core) and a dynamical part (the action). The crossed-product formalism for such an action belongs in this Part; here the action is used only through its fixed-point algebra and through the gauge-invariant uniqueness theorem below.

Uniqueness Theorems

Theorem (gauge-invariant uniqueness). Let $E$ be a countable row-finite graph and let $\phi : C^*(E) \to B$ be a $*$-homomorphism such that $\phi(p_v) \neq 0$ for every $v \in E^0$ and such that $\phi$ is gauge-equivariant, that is, there is an action $\beta : \mathbb{T} \to \operatorname{Aut}B$ with $\phi \circ \gamma_z = \beta_z \circ \phi$ for all $z$. Then $\phi$ is injective.

Proof. If $\phi$ is equivariant then it maps the core into the fixed-point algebra of $\beta$ and the spectral subspaces to spectral subspaces. On the core, which is AF, the map is injective because it is injective on the vertex projections and the core is the closed union of finite-dimensional algebras generated by finitely many vertex projections; a nonzero element of the core is detected by a finite-dimensional subalgebra, and on such a subalgebra a $*$-homomorphism that is nonzero on each minimal projection is injective. Equivariance then gives injectivity on all spectral subspaces, hence on the whole algebra. This is the gauge-invariant uniqueness theorem of Kumjian–Pask, quoted as standard.

Theorem (Cuntz–Krieger uniqueness). Let $E$ be a countable row-finite graph satisfying condition (L), and let $\phi : C^*(E) \to B$ be a $*$-homomorphism with $\phi(p_v) \neq 0$ for every $v$. Then $\phi$ is injective.

Proof. This is the Cuntz–Krieger uniqueness theorem of Kumjian–Pask: the exit condition on the cycles allows one to show that a nonzero element of the kernel would have to contain a nonzero element of the core, which is impossible by the argument of the gauge-invariant uniqueness theorem applied to the restriction to the core. It is quoted as standard.

Remark. The two uniqueness theorems divide the work as follows: the gauge-invariant theorem applies to every graph but requires the equivariance of $\phi$, while the Cuntz–Krieger theorem applies only under condition (L) but requires no equivariance, only the nonvanishing on the vertex projections. Both are injectivity criteria for maps out of a universal algebra, and both are used in practice to identify a given concrete algebra with $C^*(E)$.

Ideals, Simplicity and the Dichotomy

Theorem (gauge-invariant ideals). Let $E$ be a countable row-finite graph. The map

$$ H \longmapsto I_H = \overline{\operatorname{span}}\bigl\{s_\mu s_\nu^* : r(\mu) = r(\nu), \ s(\mu) \in H\bigr\} $$

is a bijection between the saturated hereditary subsets $H \subseteq E^0$ and the gauge-invariant closed two-sided ideals of $C^*(E)$; the quotient $C^*(E)/I_H$ is isomorphic to $C^*(E \setminus H)$, the graph algebra of the graph obtained by deleting the vertices of $H$ and all edges incident with them, and $I_H$ is the ideal generated by the projections $\{p_v : v \in H\}$.

Proof. That $I_H$ is an ideal and is gauge-invariant is a computation with the spanning theorem; that every gauge-invariant ideal arises this way is the standard argument of Kumjian–Pask, in which $H$ is recovered as the set of vertices whose projections lie in the ideal, and the saturation and hereditariness are consequences of the Cuntz–Krieger relations. The identification of the quotient with $C^*(E\setminus H)$ is by universality. The theorem is quoted as standard, and the extension to arbitrary graphs with the appropriate notion of saturated hereditary subset is due to Bates–Pask.

Corollary (simplicity). Let $E$ be a countable row-finite graph with no sinks. Then $C^*(E)$ is simple if and only if $E$ is cofinal and satisfies condition (L).

Proof. Simplicity means that the only saturated hereditary subsets are $\emptyset$ and $E^0$, which is cofinality; and one needs in addition that the ideal structure not be finer than the gauge-invariant one, which is the role of condition (L) through the Cuntz–Krieger uniqueness theorem. The precise statement and proof are those of Kumjian–Pask; it is quoted as standard.

Theorem (dichotomy). A simple graph $\mathrm{C}^*$-algebra of a countable row-finite graph with no sinks is either AF, when the graph has no cycles, or purely infinite, when it has a cycle; in particular a simple graph algebra is a Kirchberg algebra in the purely infinite case, and the classification theory of such algebras applies.

Proof. If the graph has no cycles the core exhausts the algebra and the algebra is AF by the gauge-action theorem. If there is a cycle, condition (L) produces a projection that is properly infinite, and simplicity then makes every nonzero projection properly infinite, which is pure infiniteness. The argument is standard; it is quoted.

Remark. The dichotomy theorem places graph algebras among the model algebras of the classification theory: a simple, separable, nuclear, purely infinite $\mathrm{C}^*$-algebra is classified by its K-theoretic data together with the unit class, a statement of the Kirchberg–Phillips theory whose K-theoretic content belongs in this Part. No use of that theory is made here.

Examples

The One-Loop Graph: $C(\mathbb{T})$ and the Toeplitz Algebra

Example (one vertex, one loop). Let $E$ have one vertex $v$ and one edge $e$ with $s(e) = r(e) = v$. The Cuntz–Krieger relations read $s_e^*s_e = p_v$ and $p_v = s_es_e^*$; so the generating family is a single unitary $u = s_e$ and

$$ C^*(E) = \mathrm{C}^*(u) \cong C(\mathbb{T}) , $$

the isomorphism being Gelfand duality for the unitary $u$, whose spectrum is $\mathbb{T}$. The gauge action is the shift $\gamma_z(u) = zu$, which under the identification with $C(\mathbb{T})$ is the translation action of the circle on itself.

Example (the Toeplitz algebra as a Toeplitz–Pimsner algebra). If the Cuntz–Krieger relation (K4) is dropped and only (K1)–(K3) are imposed, the universal algebra is the Toeplitz algebra $\mathcal{T}(E)$ of the graph; for the one-loop graph this is the algebra generated by a single proper isometry, hence the Toeplitz algebra $\mathcal{T}$ of Toeplitz Algebras, by Coburn's theorem there. The Cuntz–Krieger algebra $C(\mathbb{T})$ is the quotient of $\mathcal{T}$ by the compacts, and the connecting map is the Toeplitz extension

$$ 0 \longrightarrow K(H^2) \longrightarrow \mathcal{T} \longrightarrow C^*(E) \cong C(\mathbb{T}) \longrightarrow 0 . $$

For a general row-finite graph there is a Toeplitz–Pimsner algebra $\mathcal{T}(E)$ generated by a family satisfying (K1)–(K3), and $C^*(E)$ is its quotient by the ideal generated by the defects $p_v - \sum_{s(e)=v}s_es_e^*$; the resulting extension of $C^*(E)$ by the compacts generalises the Toeplitz extension. This is the standard Pimsner construction for graph algebras; the extension theory of the resulting sequence belongs in this Part.

Cuntz Algebras

Example (one vertex, $n$ loops). Let $E$ have one vertex $v$ and $n$ loops $e_1,\dots,e_n$. The relations are $s_i^*s_j = \delta_{ij}p_v$ and

$$ p_v = \sum_{i=1}^{n}s_is_i^* , $$

that is, the relations $s_i^*s_i = p_v$ and $p_v = \sum_{i=1}^{n}s_is_i^*$ of the Cuntz algebra $\mathcal{O}_n$ once the vertex projection $p_v$ is identified with the identity; so $C^*(E) = \mathcal{O}_n$. The graph has a cycle (indeed $n$ loops), it has an exit for $n \geq 2$, and it is cofinal, so $\mathcal{O}_n$ is simple and purely infinite for $n \geq 2$. For $n = 1$ the relation $p_v = s_1s_1^*$ together with $s_1^*s_1 = p_v$ makes $s_1$ unitary and one recovers $C(\mathbb{T})$, which is commutative and not purely infinite; the exit condition fails in this case, in agreement with the simplicity criterion.

Example (verification of the Cuntz relations). On the Hilbert space $\ell^2(\mathbb{N})$ with orthonormal basis $e_k$, $k \geq 0$, define $s_i e_k = e_{2k+i}$ for $i = 0,1$. Then $s_i$ is an isometry, so $s_i^*s_i = 1$, and the images of $s_0$ and $s_1$ are spanned by the even and the odd basis vectors, so $s_0s_0^* + s_1s_1^* = 1$. Both identities have been checked exactly, as index arithmetic, on the basis vectors $e_0,\dots,e_{99}$: $s_is_i^*s_i e_k = s_ie_k$ for all $k$ and $i$, and $\sum_is_is_i^*e_k = e_k$ for all $k$. The two isometries therefore present $\mathcal{O}_2$ concretely.

Example (infinitely many loops). If the single vertex has countably infinitely many loops, the sum in the Cuntz–Krieger relation is infinite and is interpreted strictly; the resulting algebra is the Cuntz algebra $\mathcal{O}_\infty$, the universal algebra generated by countably many isometries with mutually orthogonal ranges summing to $1$. It is simple and purely infinite, and the graph is cofinal with an exit at the single cycle.

Finite Acyclic Graphs: Matrix Algebras

Theorem (finite acyclic graphs). Let $E$ be a finite graph with no cycles. Then $C^*(E)$ is finite-dimensional; it is the completion of the path algebra, a finite-dimensional $\mathrm{C}^*$-algebra which is a direct sum of full matrix algebras over the strongly connected components of the path algebra, and the vertices of $E$ correspond to pairwise orthogonal projections summing to $1$.

Proof. If $E$ is finite and acyclic there are only finitely many finite paths, so the span of the monomials $s_\mu s_\nu^*$ is finite-dimensional and complete; a finite-dimensional $\mathrm{C}^*$-algebra is a direct sum of matrix algebras, and the spanning theorem identifies it with $C^*(E)$ by universality. The example of the path graph is the computation below. This is standard; it is quoted.

Example (the path graph $A_n$). Let $E$ be the path $v_1 \to v_2 \to \cdots \to v_n$ with edges $e_i : v_i \to v_{i+1}$. Then $C^*(E) \cong M_n(\mathbb{C})$, the isomorphism sending $p_{v_i}$ to the matrix unit $E_{ii}$ and $s_{e_i}$ to $E_{i,i+1}$. For $n = 2$ the monomials with $r(\mu) = r(\nu)$ are $p_{v_1}, p_{v_2}, s_{e_1}, s_{e_1}^*$, of rank $4$, and for $n = 3$ the $14$ monomials span a space of rank $9$; the computations were carried out with exact rational arithmetic on the explicit matrix units, and the rank in each case is $n^2$. The check verifies simultaneously the Cuntz–Krieger relations, the spanning theorem and the identification with the matrix algebra.

Path Spaces and the Groupoid Model

Definition. An infinite path in $E$ is a sequence $x = e_1e_2\cdots$ of edges with $r(e_i) = s(e_{i+1})$ for all $i$; the set of infinite paths is the path space $E^\infty$. The cylinder set of a finite path $\mu$ is $Z(\mu) = \{x \in E^\infty : x = \mu x'\}$.

Theorem (regular representation). Let $E$ be a countable row-finite graph with no sinks, and let $H = \ell^2(E^\infty)$ with orthonormal basis the infinite paths. For $v \in E^0$ let $p_v$ be the projection onto the paths beginning at $v$, and for an edge $e$ let $s_e$ be the partial isometry

$$ s_e\,\delta_x = \begin{cases}\delta_{ex} & \text{if } s(x) = r(e),\\ 0 & \text{otherwise},\end{cases} $$

where $ex$ denotes the path obtained by prepending $e$. Then $\{p_v, s_e\}$ is a Cuntz–Krieger $E$-family and the $*$-homomorphism it defines is injective; so $C^*(E)$ is represented faithfully on the path space.

Proof. The relations are checked directly on the basis: $s_e^*s_e$ is the projection onto paths beginning at $r(e)$, since prepending $e$ and then removing it returns $x$ and $ex$ begins with $e$; the images of distinct edges are orthogonal because their first edges differ; and the images of the edges leaving $v$ together span the paths beginning at $v$, which is (K4). Injectivity follows from the gauge-invariant uniqueness theorem applied to the gauge action evaluated on the path space, or from the Cuntz–Krieger uniqueness theorem when (L) holds. This is the standard path-space representation; it is quoted.

Remark (the groupoid model). The path space with the shift and the cylinder sets carries the structure of an ample, amenable, locally compact groupoid $G_E$, the graph groupoid of Kumjian–Pask–Renault, and the representation above is the regular representation of that groupoid, so $C^*(E) \cong C^*(G_E)$. Consequently graph algebras are groupoid algebras, and the amenability of $G_E$ gives the nuclearity of $C^*(E)$; the groupoid formalism itself belongs in this Part, and it is mentioned here only to identify the graph algebras as its principal class of examples.

Remark (K-theory and the algebraic analogue). The K-theory of a graph $\mathrm{C}^*$-algebra is computed from the graph by the six-term exact sequence associated with the Toeplitz extension; for a finite graph with no sinks and adjacency matrix $A$ the result takes the form $K_0(C^*(E)) \cong \operatorname{coker}(A^T - I)$ and $K_1(C^*(E)) \cong \ker(A^T - I)$. The computation and its consequences for the classification of graph algebras belong in this Part, and no K-theoretic result is used in this article. The purely algebraic counterpart, the Leavitt path algebra $L_K(E)$ over a field, is defined by the same relations in a purely algebraic setting and shares the combinatorial ideal structure; it is a standard object of algebra which is not part of this corpus's menu, and it is cited from the literature.

Summary

A directed graph $E = (E^0,E^1,r,s)$ has vertices, edges and the range and source maps; a finite path $\mu = e_1\cdots e_k$ satisfies $r(e_i) = s(e_{i+1})$ and has source $s(\mu) = s(e_1)$ and range $r(\mu) = r(e_k)$, a cycle is a path with $s(\mu) = r(\mu)$, and the graph satisfies condition (L) if every cycle has an exit; a row-finite graph has finitely many edges leaving each vertex, and $H \subseteq E^0$ is hereditary and saturated when it is closed under the range of an edge starting in $H$ and under the saturation condition at non-sinks. A Cuntz–Krieger $E$-family $\{p_v, s_e\}$ satisfies $p_vp_w = \delta_{vw}p_v$, $s_e^*s_f = \delta_{ef}p_{r(e)}$, $s_es_e^* \leq p_{s(e)}$ and the Cuntz–Krieger relation $p_v = \sum_{s(e)=v}s_es_e^*$ at every non-sink; the graph $\mathrm{C}^*$-algebra $C^*(E)$ is the universal algebra generated by such a family, it exists and is unique for countable row-finite graphs, and it is the closed span of the monomials $s_\mu s_\nu^*$ with $r(\mu) = r(\nu)$.

The gauge action $\gamma_z(p_v) = p_v$, $\gamma_z(s_e) = zs_e$ is a circle action whose fixed-point algebra, the core $C^*(E)^\gamma$, is AF, spanned by the monomials with $\lvert\mu\rvert = \lvert\nu\rvert$. The gauge-invariant uniqueness theorem states that an equivariant $*$-homomorphism that is nonzero on the vertex projections is injective, and the Cuntz–Krieger uniqueness theorem states the same without equivariance when condition (L) holds. The gauge-invariant ideals correspond bijectively to the saturated hereditary subsets $H \subseteq E^0$, the ideal $I_H$ being generated by $\{p_v : v \in H\}$ with quotient $C^*(E\setminus H)$; consequently $C^*(E)$ is simple exactly when $E$ is cofinal and satisfies (L), and a simple graph algebra is AF when the graph has no cycles and purely infinite when it has one. The fundamental examples are the one-loop graph with $C^*(E) \cong C(\mathbb{T})$ and its Toeplitz algebra $\mathcal{T}(E) = \mathcal{T}$ with the Toeplitz extension $0 \to K \to \mathcal{T} \to C(\mathbb{T}) \to 0$; the $n$-loop graph with the Cuntz algebra $\mathcal{O}_n$, realised on $\ell^2(\mathbb{N})$ by $s_ie_k = e_{2k+i}$, and $\mathcal{O}_\infty$ for infinitely many loops; and a finite acyclic graph with a finite-dimensional algebra, the path graph $A_n$ giving $M_n(\mathbb{C})$. The path space $E^\infty$ carries the regular representation of $C^*(E)$ and the graph groupoid $G_E$ of Kumjian–Pask–Renault, so $C^*(E) \cong C^*(G_E)$ is a groupoid algebra and is nuclear and separable.

Summary of Notation

Symbol	Meaning
$E = (E^0, E^1, r, s)$	Directed graph with vertices, edges, range, source
$E^*$, $E^k$, $E^\infty$	Finite paths, paths of length $k$, infinite paths
$s(\mu)$, $r(\mu)$, $\lvert\mu\rvert$	Source, range and length of a path
(K1)–(K4)	The Cuntz–Krieger relations
$\{p_v, s_e\}$, $s_\mu$	Generating family; path monomial
$C^*(E)$	Graph $\mathrm{C}^*$-algebra (Cuntz–Krieger algebra)
$\gamma$, $C^*(E)^\gamma$	Gauge action; core (AF algebra)
$H$, $I_H$	Saturated hereditary subset; associated gauge-invariant ideal
(L)	Condition: every cycle has an exit
$\mathcal{T}(E)$	Toeplitz–Pimsner algebra of the graph
$\mathcal{O}_n$, $\mathcal{O}_\infty$	Cuntz algebras
$G_E$	Graph groupoid
$L_K(E)$	Leavitt path algebra over a field $K$

Graph C*-Algebras