Finding an algorithm in a graph

Question

Mathematics

Good afternoon.
I'm not a programmer, but it so happened that I have to solve a non-trivial abstract problem. To concretize it, I tried to present it in the form of a graph.
So:
There is an unweighted, connected, undirected graph. Graph order = 2^N.
Graph size = 2^N * (N+1). Moreover, each vertex has N edges and another loop. (in the size of the graph, I counted the loop as one edge - so (N+1), I don't know if this is correct). The edges of the graph connect the vertices according to a previously known algorithm.
To formulate the problem, I must now give an analogy. Let's say there are N school classes. And there is a large dorm with 2^N rooms. Accordingly, each room is connected to N other rooms. Each room can accommodate one student. Each student is a member of any one class. But the number of students in the class can be different. I myself can distribute the students into classes.
And now the task is to place schoolchildren in rooms in such a way that, having got into any room, I could reach any classroom in one transition. A classroom is a room where a student from this class sits. Those. they tell me - class number 16. I see that there are 10 rooms in which schoolchildren from class number 16 are sitting, and I can get into at least one such room by making only one transition.
And yet - I can just stay in the room if I'm already in the very room that I need (there are just loops for this).
I can't formulate this problem in terms of graphs. I remember graphs from the University simply as a concept, but, unfortunately, I did not feel them then. Now I'm trying to figure it out, but I understand that without advice I can hardly cope.
Once again I will say that I am not a programmer. But I really want to get to the bottom of this problem somehow. Please advise how to be.

Answer 1

try to duplicate the question on codeforces.ru I re-read the wording twice, but did not understand. The guys there are smarter.

Answer 2

If I understand everything correctly, then there should be a student in each room and each room is connected to exactly N rooms.
In this case, you can simply sort through all the rooms in turn.
When considering the next room, we look at what neighbors are and place the student in this room randomly, but so that his class does not coincide with any of the classes of neighbors.
Thus, no matter what room you enter, you can always go to a room with a student from a given class.
It is more difficult to prove that such an arrangement is possible at all, you can look in the direction of coloring the vertices

Answer 3

As far as I understand, you need to color the vertices of an N-dimensional cube (otherwise, how to explain 2^N vertices and N edges?) in K colors so that in the 1-neighborhood of any vertex (i.e., itself plus all its neighbors) there are all colours.
The task is very similar to error-correcting codes. But there is usually a dual condition - that in the 1-neighborhood of any vertex, each color occurs at most once.
If N=2^m-1, then the problem has an exact solution (c K=N+1), it is described by the Hamming code : we paint all code words in one color, and we get the set of vertices of each other color from code words using XOR with a constant (its own for each color).
For other N one has to think. But this makes sense only if I understand the problem correctly.