The Riemann-Hurwitz formula for regular graphs

Posted on by

A little over 10 years ago, M. Baker and S. Norine wrote a terrific paper on harmonic morphisms between simple, connected graphs (see “Harmonic morphisms and hyperelliptic graphs” – you can find a downloadable pdf on the internet of you google for it). Roughly speaking, a harmonic function on a graph is a function in the kernel of the graph Laplacian. A harmonic morphism between graphs is, roughly speaking, a map from one graph to another that preserves harmonic functions.

They proved quite a few interesting results but one of the most interesting, I think, is their graph-theoretic analog of the Riemann-Hurwitz formula. We define the genus of a simple connected graph \Gamma = (V,E) to be

{\rm genus}(\Gamma) = |E| - |V | + 1.


It represents the minimum number of edges that must be removed from the graph to make it into a tree (so, a tree has genus 0).

Riemann-Hurwitz formula (Baker and Norine): Let \phi:\Gamma_2\to \Gamma_1 be a harmonic morphism from a graph \Gamma_2 = (V_2,E_2) to a graph \Gamma_1 = (V_1, E_1). Then

{\rm genus}(\Gamma_2)-1 = {\rm deg}(\phi)({\rm genus}(\Gamma_1)-1)+\sum_{x\in V_2} [m_\phi(x)+\frac{1}{2}\nu_\phi(x)-1].

I’m not going to define them here but m_\phi(x) denotes the horizontal multiplicity and \nu_\phi(x) denotes the vertical multiplicity.

I simply want to record a very easy corollary to this, assuming \Gamma_2 = (V_2,E_2) is k_2-regular and \Gamma_1 = (V_1, E_1) is k_1-regular.

Corollary: Let \Gamma_2 \rightarrow \Gamma_1 be a non-trivial harmonic morphism from a connected k_2-regular graph
to a connected k_1-regular graph.
Then

\sum_{x\in V_2}\nu_\phi(x) = k_2|V_2| - k_1|V_1|\deg (\phi).

Leave a Reply