I would like to find all graphs or lattices which satisfy the following conditions:

(1) Graph is bipartite with vertex types $A$ and $B$ ($A$-vertices only connected to $B$-vertices and vice-versa)

(2) All edges have coloring either $x$ or $y$, with $x\neq y$

(3) Degree at $A$-vertices: $p = p_x + p_y$, where $p_x$ = number of edges at an $A$-vertex with coloring $x$ and $p_y$ = number of edges with coloring $y$

(4) Degree at $B$-vertices: $q = q_x + q_y$, where $q_x$ = number of edges at a $B$-vertex with coloring $x$ and $q_y$ = number of edges with coloring $y$

(5) Require that $\displaystyle \frac{p_x}{p_y} > 1$, and $\displaystyle \frac{q_x}{q_y} < 1$

Graph may have finite or infinite number of vertices (finite graphs do not need to satisfy the degree requirement on the boundary vertices, but the number of bulk vertices should be $\gg1$)

A special case that can be considered is: $p = q$, $p_x = q_y$, $p_y = q_x$

**• Which graphs satisfy conditions (1)–(5)?**

From looking at various graphs by hand, the only graph I've found which satisfies these conditions is the Bethe lattice in the infinite case or the Cayley tree in the finite case. Are there others as well?

Some graphs which do *not* work are the (hyper)cubic lattice, the hexagonal lattice, and the Penrose tiling.

**• If the Bethe lattice and Cayley tree are the only graphs which satisfy these conditions, how would one prove that?**