Graphs, trees and simplicial complexes · DL Ferrario's Test Web Page

Graphs, trees and simplicial complexes

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)$).

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)


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

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)

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

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)


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$.