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\).


Problem Loading...

Note Loading...

Set Loading...