Если я все правильно понял, то в каждой комнате должно сидеть по ученику и каждая комната соединена ровно с N комнатами.
В таком случае можно просто перебирать по очереди все комнаты.
При рассмотрении очередной комнаты смотрим какие есть соседи и поселяем в данную комнату ученика рандомно, но так чтобы его класс не совпадал ни с одним из классов соседей.
Таким образом в какую бы комнату вы не вошли вы всегда сможете перейти в комнату с учеником из заданного класса.
Доказать что такое размещение вообще возможно, сложнее, можно посмотреть в сторону
раскраски вершин 
