The Control Room Riddle

We claim that:

$n(m) = \begin{cases} 2 & \text{if \$m = 1\$} \\ m+3 & \text{if \$m\$ is odd, \$m > 1\$} \\ \text{undefined} & \text{if \$m\$ is even} \end{cases}$

For the special case $m = 1$ , it's enough to have 2 vertices; just connect them. Clearly it's impossible with only 1 vertex, since this sole vertex must be adjacent to something else.

For odd $m > 1$ , note that the sum of degrees of all vertices must be even (degree sum formula or double counting; each edge contributes two to the sum). But this sum is equal to $1 + (n-1)m$ ; 1 for the odd vertex, and $m$ for each of the remaining $n-1$ vertices. Since $m$ is odd, we must have $n-1$ odd, so $n$ even. Additionally, we also need $n > m$ ; in a simple graph, the degree of a vertex must be strictly less than the number of vertices (there are only $n-1$ other vertices, so the degree must be no greater than $n-1$ ). Thus the candidates are $m+1, m+3, \ldots$ .

$n = m+1$ vertices aren't enough. $n-1 = m$ of the vertices must be adjacent to $m$ other vertices; since there are only $m$ other vertices, these $m$ vertices are adjacent to all other vertices. But this means the odd vertex is adjacent to all these $m$ vertices, impossible.

$n = m+3$ is easy to make. Label the vertices $v_0, v_1, v_2, \ldots, v_{m+2}$ . Let $v_0$ be adjacent to $v_m$ . $v_m$ is adjacent to everything other than $v_{m+1}$ and $v_{m+2}$ . For $0 < 2i-1 < m$ , $v_{2i-1}$ is adjacent to everything other than $v_0$ and $v_{2i}$ , and for $0 < 2i < m$ , $v_{2i}$ is adjacent to everything other than $v_0$ and $v_{2i-1}$ . $v_{m+1}, v_{m+2}$ are both adjacent to everything other than $v_0$ and $v_m$ . It can be verified that this works.

For even $m$ , we can again apply the degree sum formula. The sum of degrees is $1 + (n-1)m$ , which must be even. But $m$ is even, so this sum is always odd, contradiction. Thus $n(m)$ is not defined for even $m$ .

Finally, we just plug in: $n(7) + n(21) = (7+3) + (21+3) = \boxed{34}$ .

Relevant wiki: Graph Theory

Consider the last $n-1$ nodes, each with degree $m$ to conclude $(n-2)m+ m-1 \stackrel{(a)}{=} 2 |E| \stackrel{(b)}{\leq} 2\binom{n-1}{2}= (n-1)(n-2),$ where the equality (a) follows from the Handshaking lemma and (b) follows from the maximum number of edges in a graph with $n-1$ nodes. From the equality (a) it follows that $m$ must be odd and $n$ must be even. Plugging in $m=7,21$ we get the minimum values of $n$ , which is not difficult to see to be feasible.

Relevant wiki: Graph Theory

The general formula for $n$ is:

$n(m) = m + 3$ ; $\forall$ odd $m \geq 3$

Let the number of edges on a graph be $k$ .
An important observation is to note that

$k = \frac{(n-1)*m + 1}{2}$ .

This immediately allows us to eliminate all even $m$ . Because if $m$ is even, then $k$ won't be an integer. Hence no solution exists for even $m$ .

It is also a trivial observation that a valid graph will have atleast $m+1$ nodes.
Our proposed answer is $m+3$ . So, first we prove that $m+2$ can never be a solution:

That is very easy. Again just substitute $n = m + 2$ into the equation for $k$ . Using the fact that $m$ is odd, prove that $k$ will not be an integer. Hence $m+2$ can never be a solution.

Next we consider our proposed solution of $n = m + 3$ . In this case, we can always construct a valid solution as follows:

Let the rooms be labelled as $x_{1}, x_{2}, ... x_{m+3}$ .

• $x_{1}$ is the control room.
• $x_{2}$ is the room connected to the control room.
• Consider rooms $x_{3}$ through $x_{m+1}$ . Connect each of these rooms to $x_{2}$ . Now, the connectivity of $x_{1}$ and $x_{2}$ has been satisfied.
• Now connect rooms $x_{3}$ through $x_{m+1}$ to each other. For example, $x_{5}$ is now connected to each of $x_{3}, x_{4}, x_{6}, ... x_{m+1}$ .
• This leaves us with two nodes to consider: $x_{m+2}$ and $x_{m+3}$ . Connect both of these to each other. Then connect both of these to each of $x_{3}, x_{4}, x_{5}, ... x_{m+1}$ . Note that the connectivity of $x_{m+2}$ and $x_{m+3}$ is now satisfied.
• But now one can note that each of $x_{3}$ through $x_{m+1}$ is connected to $m+1$ nodes instead of $m$ . To rectify this, pair up the nodes $x_{3}$ through $x_{m+1}$ . And delete the edge connecting these paired up nodes. For example, pair up $x_{3}$ with $x_{4}$ and $x_{5}$ with $x_{6}$ ... and delete the edge connecting $x_{3}$ with $x_{4}$ and delete the edge connecting $x_{5}$ with $x_{6}$ ...

We have created a valid graph!

Having proven our result,
$n(7)+ n(21) = (7 + 3) + (21 + 3) = \mathbf{34}$