# Graphs, trees and simplicial complexes

2016-11-04 ( 2016-11-04)## Graphs and simplicial complexes

A one-dimensional simplicial complex is a *graph*.
That is, $K=(X_ K,\Phi_ K)$ where $V(K) = X_ K$ is the set of vertices
and $\Phi_ K$ is the set of simplexes,
with $\Phi_ K = \Phi^1_ K \cup \Phi^0_ K$, where
$E(K) = \Phi^1_ K$ are the 1-dimensional simplexes (termed *edges* of $K$)
and $\Phi^0_ K = \{ \{P\} : P \in X_ K \}$ are the $0$-dimensional simplexes (sometimes
termed again *vertices* of $K$).

A *subgraph* $X \subset K$ is a graph with as vertices
a subset of vertices of $K$, and as edges
a subset of the edges of $K$.

A *path* (walk?) in $K$ of length $l$ form a vertex $P_ 0\in X_ K$
to a vertex $P_ l \in X_ K$ is a sequence $P_ 0, \ldots, P_ l$
of $l+1$ vertices such such that for each $j=0,\ldots, l-1$
$$
\{ P_ j, P_ {j+1} \} \in \Phi^1_ K.
$$
If the vertices $P_ 0, \ldots, P_ {l}$ are all **distinct** (except possibly $P_ 0 = P_ l$), then the path
is a *simple path*.

**Remark**: This terminology is not uniform in the literature. For many authors, paths
in graph theory are what here we call simple paths.
Note that if $x,y$ are vertices and there exists a path
from $x$ to $y$ of length $l$, then
there exists a simple path from $x$ to $y$ of length $\leq l$.
In fact, assume that there is a path $x=P_ 0, \ldots, P_ l=y$.
If it is not simple, then there exists indices $i,j$
such that $i < j$ and $P_ i = P_ j$. Hence there is a path
$x=P_ 0, \ldots, P_ {i-1}, P_ i=P_ j, P_ {j+1}, \ldots , P_ k =y$
skipping all indices between $i$ and $j$, with length $<l$.
By a finite number of iterations, the path will have no multiple vertices
except the endpoints $x$ and $y$.

**Definition:** $K$ is *connected* if there is a path between any two of its vertices.

Let $\partial_ 1\from C_ 1(K) \to C_ 0 (K)$ be the unique non-trivial boundary homomorphism in the simplicial chain complex of $K$.

**Definition:** $K$ is *acyclic* if $\partial_ 1\from C_ 1(K) \to C_ 0(K)$
has trivial kernel $Z_ 1(K) = \ker \partial_ 1 = 0$.

In graph theory, a *cycle* in $K$ is a subgraph of $K$ where each vertex belongs to exactly two
(neighbouring) edges. If it not difficult to see that if there is such a cycle,
then it represents a non-zero algebraic cycle in $C_ 1(K)$, and hence
$Z_ 1(K) \neq 0$. We sometimes use the terms *geometric cycle* (the subgraph)
and *algebraic cycle* (the element of $Z_ 1(K)$).

- (1)
- A graph $K$ is acyclic $Z_ 1(K) = 0$ if and only if it does not contain a geometric cycle, i.e. a
**subgraph**where each vertex belongs to exactly two edges.

*Proof:*
Since a geometric non-trivial cycle is an algebraic cycle,
if $Z_ 1(K) = 0 $ then there cannot be grometric cycles, and
the "only if" part is proven.
For the "if" part: assume $z\in Z_ 1(K)$ is such that
$$
z = \sum_ {j=1}^l \alpha_ j[P_ j,P_ {j+1}], \quad \forall j, \alpha_ j \neq 0
$$
Let $S$ denote the set of all the $l$ edges ($1$-simplices) appearing in the sum of $z$.
The vertices $P_ 1,\ldots, P_ {l+1}$ need not be distinct. Let $X$ be the subgraph
with as vertices the set
of vertices of the edges in $S$,
and as edges the elements of $S$.
Note that each vertex in $X$ belongs to at least two edges: if
on the contrary there exists $j$ (or $j+1$) such that $[P_ j,P_ {j+1}]$
is the only edge in $S$ containing $P_ j$ (or $P_ {j+1}$),
then in the sum $\partial_ 1(z)$ the term $P_ j$ (or $P_ {j+1}$)
has as coefficient $\pm \alpha_ j \neq 0$, which is not possible
since $\partial_ 1(z) = 0$.

Now, take $[P_ 1,P_ 2]$. There exists an edge $\sigma \in S$ such that $P_ 2 \in \sigma$ and $\sigma \neq [P_ 1,P_ 2]$, and let (permuting indices if necessary) assume $\sigma = [P_ 2, P_ 3]$. Now, if $P_ 3 = P_ 1$, then $P_ 1, P_ 2, P_ 3$ together with the three consecutive edges is a geometric cycle, and we finish. Otherwise, $P_ 3 \not\in \{ P_ 1, P_ 2\}$ (i.e. the three vertices are distinct), and there exists (up to permuting indices if necessary) $P_ 4\not\in \{ P_ 2, P_ 3 \}$ such that $[P_ 3, P_ 4] \in S$. Either $P_ 4 \in \{ P_ 1\}$ or not. If yes, then there is the geometric cycle $P_ 1, P_ 2, P_ 3, P_ 4$ (with proper edges). If not, then $P_ 1, P_ 2, P_ 3, P_ 4$ are all distinct; furthermore there is $P_ 5 \not\in \{ P_ 3, P_ 4 \} $ such that $[P_ 4, P_ 5]\in S$. If $P_ 5 \in \{P_ 1, P_ 2\}$, then we obtained a cycle $P_ 1P_ 2 P_ 3 P_ 4 P_ 5$ (or $P_ 2 P_ 3 P_ 4 P_ 5$. If not, then $P_ 1, \ldots, P_ 5$ are all distinct.

We proceed in this way, and either we stop with a geometric cycle, or we obtain a sequence of distinct vertices
$P_ 1, \ldots, P_ n$ such that $[P_ j, P_ {j+1}] \in S$ for each $j$.
Since $S$ is finite, the iteration has to stop at most in $l$ steps.
*(/Proof)*

## Trees

**Definition:** A *tree* $T$ is a connected acyclic graph.

- (2)
- A connected graph $K$ is acyclic if and only if any two vertices can be connected by a unique simple path.

*Proof:*
First, assume that $K$ is connected and $x$, $y$ are two vertices of $K$.
Since $K$ is connected, there is a simple path
from $x$ to $y$.
If there are two distinct simple paths
from $x$ to $y$,
$$
x=P_ 0, \ldots, P_ l = y, \quad
x=Q_ 0, \ldots, Q_ k = y,
$$
then $$ z = \sum_ {j=0}^{l-1} [P_ j,P_ {j+1} ] - \sum_ {i=0}^{k-1} [Q_ i, Q_ {i+1}] \neq 0
$$
but
$\partial_ 1 z = -x + y + x - y = 0$,
hence $z \in Z_ 1(K) \neq 0 $.
Therefore $K$ is not acyclic.

On the other hand, if $K$ is not acyclic, there exists a geometric cycle in $K$, and two vertices
joined by two distinct simple paths.
*(/Proof)*

- (3)
- A connected graph $K$ contains as subgraph a tree $T$ having as vertices the same set of vertices of $K$ (a
*spanning tree*). It is maximal in the family of all subgraphs of $K$ wich are trees.

*Proof:*
Let $X$ be the set of all subgraphs of $K$ which are trees, ordered by inclusion.
Such a set of subgraphs is finite and partially ordered, and hence it has maximal elements.

Let us show that a tree $T\subset K$ is maximal in $X$ if and only if it is a spanning tree,
i.e. if and only if its vertices are the same as the vertices of $K$.

If the set of vertices of $T$ coincides with the set of vertices of $K$, and $T' \subset K$ is another tree such that $T\subset T'$, $T \neq T'$, then there exists an edge $[P,Q] \subset T'$ such that $[P,Q] \not\subset T$. But there is a (unique) simple path from $P$ to $Q$, which yield a cycle in $T'$ together with the edge $[P,Q]$: this is impossible since $T'$ is a tree and hence acyclic.

On the other hand,
if the set of vertices of $T$ does not coincide with the set of vertices of $K$,
then there exists $Q$ vertex of $K$ such that $Q \not \in T$.
Take $P \in T$, and $P=P_ 0, \ldots, P_ l = Q$ a simple path
in $K$ (which is connected). Let $j$ be the minimum value of the index
such that $P_ j \in K$ but $P_ {j+1} \not\in K$.
The edge $\sigma = [P_ j, P_ {j+1}]$ is not contained in $T$,
hence the subgraph $T' = T \cup [P_ j, P_ {j+1}]$
is not equal to $T$.

Now, if $X\subset T'$ is a geometric cycle,
then it cannot contain $[P_ j, P_ {j+1}]$ (since the only edge of $T'$
containing $P_ {j+1}$ is $\sigma$), and therefore
$X \subset T$.
But $T$ is a tree, and hence it does not have cycles.
Thus, $T'$ is acyclic. It is easy to show that $T'$ is connected,
and hence that it is a tree, and that $T$ is not maximal.
*(/Proof)*

## Homology of a graph

- (4)
- The homology groups of a
**connected**graph $K$ are: $$ H_ 0(K) = \ZZ, \quad H_ 1(K) = \ZZ^{h_ 1} $$ where $h_ 1 =c_ 1 - c_ 0+1$, with $c_ 0$ is the number of vertices of $K$, $c_ 1$ is the number of edges of $K$.

*Proof:*
Let $T\subset K$ be a spanning tree, with -say- $l+1$ vertices.
By definition, $Z_ 1(T) = 0$.
Let $R$ be a vertex of $T$.
It is possible to define an ascending chain of trees
$\{R\} = T_ 0 \subset T_ 1 \subset \ldots \subset T_ l = T$,
such that the $j$-th tree $T_ j$ has $j+1$ vertices.
Let $P_ j$ denote the vertex of $T_ j $ which is not in $T_ {j-1}$ (if $j=0$,
$P_ 0 =R$). Such a vertex, for $j>0$, belongs to a unique edge in $T_ j$:
let $P_ j'$ be the other vertex of such a simplex.
Hence $T_ j$ has $j+1$ vertices and $j$ edges, and therefore
$T$ has $c_ 0$ vertices (the same as $K$), and $c_ 0-1$ edges (after $R$,
$T$ is obtained by adding iteratively $l$ edges). Let $Y$ denote the set of edges
of $K$ which are **not** in $T$: it has $r= c_ 1 - (c_ 0 - 1)= c_ 1 - c_ 0 + 1$ elements.
Let $\pi \from C_ 1(K) \to \ZZ[Y]\cong \ZZ^r $
denote the projection, defined as
$$
\pi(\sigma) =
\begin{cases}
\sigma & \text{if $\sigma \in Y$} \\

0 & \text{otherwise}
\end{cases}
$$
Then $\ker \pi \cap Z_ 1 (K) = 0$: in fact, if $z \in \ker \pi \cap Z_ 1 (K) = 0$,
then
as $\pi (z) = 0$, the support of $z$ is in $T$. Hence $z\in Z_ 1(T) = 0$,
and therefore $z=0$.
Therefore, the restriction of $\pi$ to $Z_ 1(K)$ is a monomorphism
$Z_1 (K) \to \ZZ[Y]$.

It is also onto: for any edge $\sigma =[x,y]\in Y$, its vertices $x,y$ belong to $T$. There is a unique simple path in $T$ from $x$ to $y$, say $x=P_ 0, \ldots P_ k = y$. Then $$ z = [y,x] + \sum_ {j=0}^{k-1} [P_ j, P_ {j+1}] \in Z_ 1(K), \text{ and } \pi(z) = [y,x] = -\sigma. $$ Thus $H_ 1(K) = Z_ 1(K) = \ZZ^{r}$.

The $0$-dimensional homology of any connected graph is $\ZZ$: consider the augmentation homomorphism $\varepsilon \from C_ 0(K) \to \ZZ$, defined as $\varepsilon [P] = 1$ for each vertex $P$. Fix a vertex $R$ of $K$ For each $j=1, \ldots, c_ 0$, let $P_ j$ denote the $j$-th vertex in $K$, and let $P_ i^j$ (as $i=0,\ldots, l_ j$) denote the simple path such that $P_ 0^j = R$, and $P_ {l_ j}=P_ j$ Then, for each $j$ $$ \partial_ 1 \left( [P_ 0^j,P_ 1^j] + \ldots [P_ {l_ j-1}^j,P_ {l_ j}^j] \right) = [P_ {l_ j}^j] - [ P_ 0^j ] = [P_ j] - [R ]. $$ Let $p_ j$ denote the sum $$p_ j = [P_ 0^j,P_ 1^j] + \ldots [P_ {l_ j-1}^j,P_ {l_ j}^j].$$

Hence
if $z = \sum_ {j=1}^ {c_ 0} \alpha_ j [P_ j] \in \ker \varepsilon$,
$$ z = \sum_ {j=1}^ {c_ 0} \alpha_ j ([P_ j] - [R]) =
= \sum_ {j=1}^ {c_ 0} \alpha_ j (\partial_ 1 p_ j) \in B_ 0(K)
$$
is a boundary. Therefore $B_ 0(K) = \ker \epsilon$, and
$H_ 0(K) = \ZZ$.
*(/Proof)*

$\newcommand{\rk}{\operatorname{rank}}$

**Remark:**
Given a short exact sequence of abelian groups $0\to A \to B \to C \to 0$,
one has $\rk B = \rk A + \rk C$.
Now, consider the two exact sequences
$$
0 \to B_ j \to Z_ j \to H_ j \to 0
\implies
\rk Z_ j = \rk B_ j + \rk H_ j
$$
$$
0 \to Z_ {j} \to C_ j \to B_ {j-1} \to 0
\implies
\rk C_ j = \rk Z_ j + \rk B_ {j-1},
$$
which implies
$$\begin{aligned}
\sum_ {j} (-1)^j \rk C_ j & =
\sum_ {j} (-1)^j ( \rk Z_ j + \rk B_ {j-1}) = \\

&= \sum_ {j} (-1)^j \left( \left( \rk B_ j + \rk H_ j \right) + \rk B_ {j-1} \right) = \\

&=
\sum_ {j} (-1)^j \rk B_ j +
\sum_ {j} (-1)^{j+1} \rk B_ j +
\sum_ {j} (-1)^j \rk H_ j \\

&=
\sum_ {j} (-1)^j \rk H_ j
\end{aligned}
$$
which in our context is $c_ 0 - c_ 1 = h_ 0 - h_ 1$.