Mr. Dlanod is back

First we need to convince ourselves that a cycle by itself satisfies the budget constraint; otherwise there would be no solution. Consider a cycle $1 \rightarrow 2 \rightarrow 3 \rightarrow ... \rightarrow n \rightarrow 1$ , and assume that there are $x_k$ patrons at hotel $k$ in a given week. If we let $x_{n+1} = x_1$ , then the overall profit will be $\sum_k x_k^2 - \sum_k x_kx_{k+1}=\frac{1}{2}\sum_k(x_k-x_{k+1})^2\geq 0$ , showing that a cycle "works." (We merely break even if and only if the number of patrons happens to be the same at all the hotels.)

Thus one possible option is to run a loop road past all the six hotels. We claim that this is the only solution. Indeed, if a loop would run past fewer than six hotels, then there would be at least one "outlier" connected to at least one of the hotels on the loop. If all the hotels on the loop get 2 patrons but the outlier gets only 1 (with all the other hotels, if any, getting no customers that week), then Dlanod would suffer an overall loss of at least 1 Ruble, which is verboten.

Thus there is $\boxed{1}$ isomorphism class of graphs with the required properties.

If $G$ is a connected graph on six hotels/vertices that fits Dlanod's requirements, we can find a nonempty subcollection $U$ of the vertices of $G$ such that, if $G_0$ is the graph obtained from the vertices $U$ and all the edges of $G$ that connect two vertices of $U$ , then

• $G_0$ is a connected subgraph of $G$ such that every vertex of $G_0$ has degree $2$ or more,
• $U$ is maximal in that no larger subcollection of the vertices of $G$ can be found with the same properties.

The fact that $U$ exists follows since Dlanod requires a cycle in his network of roads.

If $x_v$ guests stay at vertex $v$ , forming the vector $\mathbf{x}$ , let $D(\mathbf{x})$ be Dlanod's profit.

We can restrict attention to $G_0$ by considering situations where $x_v = 0$ for $v \not\in U$ . If $L$ is the Laplacian matrix of $G_0$ , and if $\hat{\mathbf{x}}$ is the vector of guests at the vertices in $U$ only, then $\hat{\mathbf{x}}^TL\hat{\mathbf{x}} \; = \; 2D(\mathbf{x}) + \sum_{u \in U}\big(\mathrm{deg}(u)-2)x_u^2$ If we consider the particular case where $z_u = 1$ for all $u \in U$ (and $z_v = 0$ for $v \not\in U$ still), then $\hat{\mathbf{z}}^TL\hat{\mathbf{z}} = 0$ , and hence $D(\mathbf{z}) < 0$ if there are any $u \in U$ with $\mathrm{deg}(u) > 2$ . Thus all vertices in $G_0$ must have degree $2$ .

Suppose that $U$ is not the full set of vertices of $G$ . There must be some vertex $v$ of $G$ which does not belong to $U$ , but which is directly connected by a single edge of $G$ to $G_0$ (if there were two or more such edges, then $v$ could have been included in $U$ ). Consider putting $2$ guests in each of the vertices of $U$ , $1$ guest in $v$ , and $0$ guests everywhere else. Then Dlanod's profit is $0$ from the subgraph $G_0$ plus $1^2$ from the hotel $v$ , minus $2$ for the road connecting $v$ to $G_0$ , and $0$ from everything else. In other words, Dlanod makes a loss. Thus $U$ must be the full set of vertices, so that $G = G_0$ .

Thus all vertices must have degree $2$ , and hence $D(\mathbf{x}) = \tfrac12\mathbf{x}^T L \mathbf{x} \ge 0$ for all $\mathbf{x}$ . Since the graph is connected, this means that it must be a $6$ -cycle. Thus there is only $\boxed{1}$ option to within isomorphism

From this argument, there is nothing special about $6$ that I can see, and the same argument should work for $n$ hotels. There is at least one profitable tree configuration (a simple chain), so Dlanod has more choices if he allows himself trees.