Japan Mathematical Olympiad Initial Round

Consider a graph which consists of 4 vertices, representing 4 sub-committees, and edges, representing 4 members, each of which connects a pair of vertices, corresponding to two sub-committees a committee member prefers to serve in. Let us call a method of choosing one of the end points for each of the edges to be a good method if every vertex of the graph is chosen exactly once by the method. A method of assigning sub-committee to each member of the committee to satisfy the requirement of the problem corresponds to a good method. For each vertex of a graph, define the degree of the vertex to be the number of edges emanating from the vertex.

Let us say that a graph of 4 vertices and 4 edges as above is of type $S_0$ if there exists a good method of choosing. If a graph is type $S_0$, then since for the corresponding situation for sub-committee assignments, for any sub-committee there is a member who prefers to serve in it, every vertex of such a graph has a positive degree. Suppose there is a vertex with degree 1. Consider the operation of removing that vertex and the edge emanating from it. We note that the number of good methods of choosing does not change before and after the removal of a vertex of degree 1 and the edge emanating from it. This is because if you apply a good method to the graph before the removal of a vertex $v$ of degree 1 and the edge $\ell$ emanating from it, we have to remove that vertex $v$ when we choose a vertex to remove for the edge $\ell$. Now keep repeating the process of removing a vertex of degree 1 and the edge emanating from it, then we reach the situation where every remaining vertex has degree greater than or equal to 2. Let us say that a graph is of type $S_1$ if every vertex has degree greater than or equal to 2. Suppose in a graph of type $S_1$ there are $k$ vertices and $k$ edges. Then the sum of the degrees of all the vertices must be two times the number of edges, namely $2k$. On the other hand, every vertex has degree greater than or equal to 2, which forces each vertex to have degree 2.

Next, for a graph of type $S_1$, consider a process of starting from a vertex and tracing edges to move to different vertices without tracing in reverse direction the edge traced in the immediately preceding step. Since every vertex has degree 2, the process does not stop and eventually comes back to the starting vertex after a finite number of steps. Furthermore, every vertex passed through during this process cannot be a vertex for an edge not passed through during this operation. Therefore, we can remove all the vertices and edges passed through under this operation. Let us say that the set of vertices and edges removed in this way is a cycle. If we repeat the process of removing cycles until all the vertices and edges are removed, then we can decompose the original graph into the disjoint union of a finite number of cycles.

Next, we compute the number of good methods of choosing: if for an edge one of its vertices is chosen, then for any other edge lying in the same cycle, the choice of its end points is uniquely determined. Therefore, if there are $n$ cycles in a graph, then there are $2^n$ good methods for choosing. Since the condition of the problem asks for a configuration for which the number of good methods of choosing is 2, we see that the number of cycles must be 1.

Let us now determine the number of ways vertices and edges can be combined in a graph of type $S_0$ when the type $S_1$ graph derived from it has exactly 1 cycle. We do this by separating cases depending on the number of vertices in the cycle in $S_1$.

When the number of vertices in the cycle is 4, there are 3 ways of placing vertices, and for each placement of vertices there are $4!$ ways of placing edges. So, there are $3\cdot 4!=72$ ways of combining vertices and edges in this case.



When the number of vertices in the cycle is 3, there are $\left(\genfrac{}{}{0ex}{}{4}{3}\right)=4$ ways of choosing vertices to be included in the cycle, 3 ways to combine the remaining point to one of the vertices of the cycle and $4!=24$ ways of placing edges for each placement of vertices. Therefore, there are $4\cdot 3\cdot 24=288$ ways of combining vertices and edges in this case.





(i) When one of the 2 vertices is connected with $A$, other vertex with $B$, there are just 2 ways depending on which of the remaining vertices is connected with $A$.



(ii) When both of the vertices are connected with $A$ or both with $B$, there are 2 ways depending on whether $A$ or $B$ is the vertex to be connected.



When one of the remaining vertices, say $C$, is connected with $A$ or $B$ and the other remaining vertex is connected with $C$, there are 4 ways depending on which of the remaining vertices is $C$ (2 choices) and whether $C$ is connected with $A$ or $B$ (2 choices).



Consequently, there are $2+2+4=8$ choices for the placement of remaining 2 vertices, and the total number of placements of vertices when the number of vertices in the cycle is 2 is given by $6\cdot 8=48$. For each placement of the vertices, there are $4\cdot 3=12$ ways of choosing the ways of placing edges outside of the cycle, and therefore, there are $48\cdot 12=576$ ways of combining vertices and edges in this case.

Summarizing the results obtained above, we get $72+288+576=936$ ways of connecting vertices and edges resulting with a graph for which there are exactly 2 good methods of choosing.