# Graphs with constant edge imbalance

The imbalance of an edge $(u,v) \in E(G)$ of a graph $G$ is defined as $|d(u)-d(v)|$ ($d$ being, as usual the degree). (This concept was introduced by Albertson in 1997)

I'm interested in the set of possible imbalances in a graph. In particular I am looking for examples of graphs where all edges have the same imbalance. Regular graphs trivially have this property and so does the path $P_{3}$.

Is it true that if all edges of $G$ have the same imbalance, then $G$ is either regular or $P_{3}$?

I have an inkling that this ought to be true by some sort of pigeonhole principle but can't think up a proof. A counterexample will be even more welcome :)

-
Complete bipartite graph? – Yoav Kallus Jun 22 '13 at 21:43
More generally, any biregular graph: en.wikipedia.org/wiki/Biregular_graph – Yoav Kallus Jun 22 '13 at 21:48
You need that $G$ is connected, of course. Furthermore, there are graphs with constant imbalance that are not even biregular (for example. the graph on 7 vertices with 3 vertices of degree 1 each attached to a vertex of degree 2 each attached to a unique vertex of degree 3). – Thomas Bloom Jun 22 '13 at 23:52
And, in fact, that idea can be generalised easily to construct arbitrarily large graphs with arbitrarily large constant imbalance (take a bunch of vertices with degree 1, connect them to a bunch with degree 1+n, connect those to a bunch of 1+2n, and so on, just throwing enough vertices at each stage to make this possible). – Thomas Bloom Jun 23 '13 at 0:03
The simplest example I can think of (included in biregular graphs) is the star graph; can be arbitrarily large, and has largest possible constant imbalance. Any edge transitive, not vertex-transitive graph gives an example. – Benoît Kloeckner Jun 24 '13 at 11:07