# The Control Room Riddle

Discrete Mathematics Level 5

Find the minimum number of nodes $$n$$ on a graph, that satisfies the following properties:

• There is exactly one node that is connected to only one other node.
• And each of the remaining $$n-1$$ nodes is connected to $$m$$ other nodes.

Now, prove that a solution exists only for odd values of $$m$$. Let $$n(m)$$ denote $$n$$ as a function of $$m$$. Hence, $$n(3) = 6$$.

Find the value of $$n(7) + n(21)$$.

Note: Consider this to be a graph theory question and hence no practical notions of a room apply. Each room is nothing but a node on a graph and can be connected to any other room, and not just "adjacent" ones, as would be the case with real rooms. The graph can even be fully connected.

Inspiration: A Ted-Ed video. In the video, they consider each room to be connected to 3 other rooms. What if each room were connected to $$m$$ rooms instead? Let the number of rooms be $$n$$ in this case, in the video, $$m=3$$ yields $$n=6$$.

×