Translate into graph theory: Each cycle has even length, and the degree of all vertices is equal except for one that is smaller. It's well-known that a graph is bipartite iff it doesn't have an odd cycle. Since we don't have an odd cycle, the graph is bipartite and so we can partition the vertices into two classes so edges only run between classes. Let the sizes of the classes be $m, n$, where $n$ contains the smaller vertex. Let the common degree be $d$ and the smaller degree be $0 < c < d$. Add up the degrees on both sides; each sum counts exactly the number of edges. From the $m$ class, the sum of degrees is simply $md$. From the $n$ class, the sum of degrees is $(n-1)d + c$. Now divide both by $d$. The first number is an integer $m$; the second number is $n-1 + \frac{c}{d}$. But since $0 < c < d$, this is not an integer. That's the contradiction.