A little over 10 years ago, M. Baker and S. Norine (I’ve also seen this name spelled Norin) 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 to be
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 be a harmonic morphism from a graph
to a graph
. Then
I’m not going to define them here but denotes the horizontal multiplicity and
denotes the vertical multiplicity.
I simply want to record a very easy corollary to this, assuming is
-regular and
is
-regular.
Corollary: Let be a non-trivial harmonic morphism from a connected
-regular graph
to a connected -regular graph.
Then