I have a set of data that I would be mapped very well to the panes of a planar graph. For this to work, each vertex must have a maximum total amount of 3 neighbours. The reason for this constraint is beecause the data I am interested in mapping will contain a relation between data entries if their regions share an edge & 2 vertices, so if there is a vertex with more than 3 neighbours, it may share a vertex with another region, but not an edge.
Just constructing a lattice where each vertex has 3 nodes is not difficult, but what if I want an additional constraint: each region in the lattice must have the same amount of edges. I tried constructing a planar graph this way, and could only get 5 regions:
Which isn't really a proof that such a lattice cannot exist.
My question is, is there a minimal $k \in \mathbb{N}$ where given $n > k$ vertices, it is possible to construct a graph where each region has $k$ edges, and each vertex has at most 3 neighbours?