I had the following conjecture in combinatorics, regarding seating arrangement Let $n, m $ be odd integers of the form $5 +4k$, $k=0,1,2,$. If we have a table, seating $n*m$ guests, so that every guest knows exactly half of the other guests at their table, then we can split the table up in $n$ tables, each seating $m$ guests, so that every guest knows exactly half of other guests at their table.
Intuitively, I'm pretty confident that this conjecture is correct, but I have no idea how to prove it. Any thoughts, tips, or counterexamples are appreciated. Thanks a lot.
 A: This conjecture is incorrect and have a counterexample.
The problem can be restated in words of graph theory, like following:

Given a $\frac{nm-1}{2}$-regular graph $G = (V, E)$ such that $|V| = nm$, we can split $V$ into $n$ groups $\{V_1, V_2, \dots, V_n\}$, such that for each $i$, $|V_i| = m$ and the graph induced by $V_i$ is a $\frac{m-1}{2}$-regular graph.

As a preparation, we can assume $(n, m) = (4k+1, 4l+1)$ or $(n, m) = (4k+3, 4l+3)$ for some $k, l$. Otherwise $nm \equiv 3 \ (\mathrm{mod} \ 4)$ therefore $nm$ and $\frac{nm-1}{2}$ will be odd; there's no such regular graph.
Now we construct the counterexample graph. Let $V = \{0, 1, 2, \dots, nm-2, nm-1\}$. For $0 \leq x \lt y \leq nm-1$, we draw edges by the following conditions:

*

*Case of $y \neq nm-1$: Draw edge $xy$ if and only if $x \not\equiv y \ (\mathrm{mod} \  2)$ and $(x, y) \neq (4k, 4k+1)$ for all $k$.

*Case of $y = nm-1$: Draw edge $xy$ if and only if $x \equiv 0, 1 \ (\mathrm{mod} \ 4)$.

We can easily see that the constructed graph is $\frac{nm-1}{2}$-regular. And also, if we erase the vertex $nm-1$, the graph will be bipartite, because this part is purely constructed by parity.
However, if a induced subgraph is bipartite, it cannot be a $\frac{m-1}{2}$-regular graph. Let the partition of bipartite subgraph be $\{U_1, U_2\}$. We must hold (degree sum in $U_1$) = (degree sum in $U_2$) due to bipartiteness. However, since $m = |U_1| + |U_2|$ is odd, it is sure that $|U_1| \neq |U_2|$, so the aim of "all degrees are equal" cannot be achieved.
Since only one group can use vertex $nm$, the other $n-1$ groups will be bipartite. Such groups cannot be $\frac{m-1}{2}$-regular as said previously. So, this case is the counterexample of the conjecture.
