Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $G$ be a connected, directed graph with $v$ vertices and $e$ edges. According to Massey (Ch. VIII, Section 3), the euler characteristic satisfies \begin{align} v - e = \chi(G) = \text{rank} \, H_0(G) - \text{rank} \, H_1(G) = 1 - \text{rank} \, H_1(G). \end{align} Based on basic definitions, $H_{1}(G) = \ker \partial_1 / \text{im} \, \partial_2$, where $\partial_*$ is the (chain) boundary map. I'd like to compute $\text{dim} \ker \partial_1$ and $\text{dim} \, \text{im} \, \partial_1$.

From what I understand, if $\rho(\partial_1)$ is a matrix representation of $\partial_1$, then it has size $e \times v$. By Rank-Nullity, $\dim \ker \partial_1 + \dim \text{im} \, \partial_1 = v$. Since $G$ has no $2$-chains, then $H_1 \cong \ker \partial_1$. Thus, $\dim \ker \, \partial_1 = e- v + 1$ (also the number of circles in the homotopy type of $G$) and $\dim \, \text{im} \, \partial_1 = 2v - e - 1$.

I have a feeling that I've misunderstood something fundamental. Is my reasoning correct?

Edit: It appears that I switched rank with size, so $\dim \, \text{im} \, \partial_1 = v - 1$ consistent with the rank of $\rho(\partial_1) = v - 1$, as wckronholm points out. Now the question boils down to the following :Is $\dim \ker \partial_1 = 1$ or $e - v + 1$? It seems now it is $1$. However, $\text{rank} \, H_1(G) = 1 - \chi(G) = e - v + 1$, but $\text{rank} \, H_1(G) = \dim \ker \partial_1 - \dim \, \text{im} \, \partial_2$ and $\dim \, \text{im} \, \partial_2 = 0$, no?

share|cite|improve this question
up vote 2 down vote accepted

The graph is connected (and finite, evidently) so the rank of $H_0(G)$ is $1$. Hence $\mathrm{dim}\; H_0(G) = \mathrm{dim} \; \mathrm{ker}\; \partial_0 - \mathrm{dim} \; \mathrm{im}\; \partial_1$. But $\mathrm{dim}\;\mathrm{ker} \;\partial_0 = v$ so this gives $\mathrm{dim}\;\mathrm{im}\;\partial_1 = v-1$.

It seems to me that, using your notation, the rank of $\rho(\partial_1)$ is $v-1$.

Edited to address question edits:

As you computed above, $\mathrm{dim}\;\mathrm{ker}\; \partial_1 = e-v+1$. This is consistent with rank-nullity since $\mathrm{dim}\;\mathrm{im}\; \partial_1 + \mathrm{dim}\;\mathrm{ker}\;\partial_1 = (v-1) + (e-v+1) = e = \mathrm{dim}\; C_1(G)$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.