Proposition 4

Endowed with this law of composition, $\varpi_G$ is a groupoid.

By construction, one has the relation $\varphi (cc') =\varphi (c)\varphi (c')$, for every pair of juxtaposed paths $(c, c')$ in G. Every arrow of $\varpi_G$ is of the form $\varphi (c)$, where $c$ is a path in G. It follows that the law of composition of $\varpi_G$ is associative and that $\varphi (e_a)$ is an identity element at $a$, for every vertex $a$ of $\varpi_G$. It remains to prove that every arrow of $\varpi_G$ is invertible. Let $c$ be a path in G, and let us prove by induction on the length of $c$ that one has $\varphi (c)\varphi (\overline{c}) =\varphi (e_{o(c)})$. This equality is true if $c$ is of length 0. If $c$ is of length $n\geqslant 1$, we may write $c=c_1c_2$, with $c_1$ of length 1 and $c_2$ of length $n-1$. Then, $\overline{c}=\overline{c_2}\overline{c_1}$ and one has

by definition of the relation $\mathscr{R}$.

Applying this equality to the path $\overline{c}$, we see that $\varphi (\overline{c})\varphi (c) =$ $\varphi (e_{t(c)})$. Thus, $\varphi (c)$ is invertible, with inverse $\varphi (\overline{c})$.

The equivalence classes of the relation $\mathscr{R}$ are called the path classes in the graph G; the groupoid $\varpi_G$ is called the groupoid of path classes of the graph G. It has the same set of vertices as G, and its orbits are the connected components of the graph G.

Let us denote by $v$ the mapping which associates with an arrow $f$ of G the class of the path $(o(f), f, t(f))$ of G. The pair $j$ = (Id$_{Som(G)}, v$) is a morphism, called canonical, of quivers from G into $\varpi_G$. Its image generates $\varpi_G$; for every arrow $f$ of G, one has $j(\overline{f}) =j(f)^{-1}$.

Let G and $G'$ be graphs, let $\varphi : G\rightarrow G'$ be a graph morphism. Let us denote by $j: G\rightarrow \varpi_G$ and $j': G'\rightarrow \varpi_{G'}$ the canonical morphisms. If $c= (a_0, f_1, a_1, . . . , a_n)$ is a path in G, the class of the path $\varphi (c) = (\varphi (a_0), \varphi (f_1), \varphi (a_1), . . . , \varphi (a_n))$ depends only on the class of $c$. Thus, by passing to equivalence classes, one defines a quiver morphism $\varpi (\varphi ):\varpi_G\rightarrow \varpi_{G'}$ such that $\varpi (\varphi )\circ j=j'\circ \varphi$. It is a groupoid morphism.