**Real-life motivation.** My eldest son attended a football (soccer) class with $17$ other students, so $18$ students in total. There were $6$ students with year of birth (yob) $n$, then $6$ more with yob $n+1$ and the remaining $6$ had yob $n-1$. In the evening, my son told me that at some point, all $18$ students sat in a circle such that for every student $x$, the years of birth of $x$ and his/her two neighbors covered all $3$ possible years of birth. I found this amazing until I found a trivial solution.


**Formalization.** Let $G= (V, E)$ be a simple, undirected graph. For $v\in V$ let $N(v) = \{w\in V: \{v,w\} \in E\}$ be the set of neighbors of $v$. For a positive integer $k>1$, we call a graph $k$-*regular* if $|N(v)| = k$ for all $v\in V$. We call a $k$-regular graph *satisfying* if there is a map $f:V\to \{1,\ldots,k+1\}$ such that $$f\big(N(v)\cup\{v\}\big) = \{1,\ldots,k+1\} \text{ for all } v\in V.$$


Obviously, for any integer $k>1$ the complete graph $K\_{k+1}$ is satisfying.


**Question.** (Only the first needs to be answered for acceptance.)


1. If $k>1$ is an integer, is there a non-complete satisfying connected $k$-regular graph $G=(V,E)$?
2. If $k>1$ is an integer and $G=(V,E)$ is $k$-regular and satisfying, is $|V|$ necessarily a multiple of $k+1$?



Assigning numbers $\{1,\ldots,k+1\}$ in a balanced way in a $k$-regular graph
The satisfying graphs are precisely the [covering graphs](https://en.wikipedia.org/wiki/Covering_graph) of $K\_{k+1}$. General theory of covering spaces implies that, since $K\_{k+1}$ is connected, each point in the graph has the same number of preimages under a covering map, so every satisfying graph indeed has the number of vertices divisible by $k+1$.


The theory of covering spaces also answers the question of existence - connected covering spaces are in bijection with subgroups of the fundamental group of $K\_{k+1}$, which is free on $|E(K\_{k+1})|-|V(K\_{k+1})|+1=\frac{k(k-1)}{2}$ generators. This group has many subgroups, including many of finite index, so we get many finite satisfying $k$-regular graphs.


