9.4. In the company, some pairs of people are friends (if $A$ is friends with $B$, then $B$ is also friends with $A$). It turned out that among any 100 people in the company, the number of pairs of friends is odd. Find the largest possible number of people in such a company.

(E. Bakayev)
Answer: 101.

Solution: In all solutions below, we consider the friendship graph, where vertices are people in the company, and two people are connected by an edge if they are friends.

If the graph is a cycle containing 101 vertices, then any 100 vertices will have exactly 99 edges, so such a company satisfies the conditions of the problem. It remains to show that there cannot be a company of 102 people (then a company of more than 102 people cannot exist either). Below we provide several different ways to do this; in each way, we assume, for the sake of contradiction, that such a company has been found.

First solution. Consider an arbitrary set of 101 vertices and the induced subgraph on these vertices, let it have $k$ edges. By removing an arbitrary vertex from this subgraph (say, of degree $d$), we get 100 vertices with an odd number of edges $k-d$. Thus, the degree of any vertex in our subgraph has a parity different from the parity of $k$, meaning that the degrees of all vertices in the subgraph have the same parity. However, as is well known, in a graph with an odd number of vertices, all vertices cannot have an odd degree. Therefore, all these degrees are even, and the number of edges $k$ is odd.

Now let the entire graph with 102 vertices have $\ell$ edges. When any vertex (say, of degree $d$) is removed, we get a subgraph with an odd number of edges $\ell-d$; similarly to the above reasoning, we get that in the entire graph, all vertices have the same parity of degrees. Note that our graph cannot be empty (i.e., have no edges) or complete (i.e., have all $C_{102}^{2}$ edges), otherwise, on any 100 vertices, there will be either 0 or $C_{100}^{2}=99 \cdot 50$ edges, which is an even number. Therefore, there is a vertex connected to at least one other vertex but not to all. In other words, there are vertices $u, v_{1}$, and $v_{2}$ such that $u$ is connected to $v_{1}$ but not to $v_{2}$. The degrees of vertices $v_{1}$ and $v_{2}$ in the original graph have the same parity, so after removing $u$, they will have different parities. This is impossible by the above proof.

Second solution. There are $n=C_{102}^{2}=51 \cdot 101$ ways to remove two vertices from 102, leaving 100. Number these ways from 1 to $n$. Let $a_{i}$ be the number of edges on the remaining 100 vertices in the $i$-th way; by assumption, all numbers $a_{i}$ are odd, and thus their sum $S$ is also odd (since the number $n$ is odd).

On the other hand, consider any edge $uv$. This edge is counted in the number $a_{i}$ exactly when vertices $u$ and $v$ are not removed in the $i$-th way, i.e., when some pair of the remaining 100 vertices is removed. This happens in $k=C_{100}^{2}=50 \cdot 99$ ways. Thus, each edge is counted in $S$ an even number of times $k$, so $S$ must be even. Contradiction.

Third solution. Call a vertex even if its degree is even, and odd otherwise. Consider two cases.

Case 1. Suppose the total number of edges in the graph is odd. Then, by removing any pair of vertices, we must remove an even number of edges (to leave an odd number). On the other hand, if we remove vertices with degrees $d_{1}$ and $d_{2}$, the number of removed edges is $d_{1}+d_{2}$ if these vertices are not connected by an edge, and $d_{1}+d_{2}-1$ if they are connected. Therefore, vertices of the same parity are never connected by an edge, and vertices of different parities are always connected.

Thus, if the graph has $k$ even vertices and $\ell$ odd vertices, even vertices have (even) degree $\ell$, and odd vertices have (odd) degree $k$. This is impossible, since $k+\ell=102$.

Case 2. Suppose the total number of edges in the graph is even. Similarly, we get that vertices of the same parity are always connected by an edge, and vertices of different parities are never connected. Therefore, if the graph has $k$ even vertices and $\ell$ odd vertices, even vertices have (even) degree $k-1$, and odd vertices have (odd) degree $\ell-1$. This again contradicts the equality $k+\ell=102$.

Remark. Of course, there are other examples of a company of 101 people satisfying the condition.

Comment. The statement that in any graph, the number of vertices of odd degree is even, is accepted without proof.

Only the answer -0 points.

Only an example of a company of 101 people satisfying the condition is provided -1 point.

Noting only that to complete the solution, it is sufficient to show that the company cannot have exactly 102 people does not add points. If this observation is missed in the solution, points are not deducted.

Proving only that the company cannot have 102 people -6 points.

Below are some advances in proving this fact. Points for different advances do not add up; 1 point can be added for a correct example of a company of 101 people.

Proving only that in any company of 101 people satisfying the condition, all vertex degrees have the same parity -2 points.

In addition to this, proving that in the entire company of 102 people, all vertices have the same parity -4 points.

Proving that the graph is either a complete bipartite graph or the union of two complete graphs (as shown in the third solution) -4 points.

If one of the above cases is missed (without sufficient reason) -3 points instead of 4.

Only one of the two cases from the third solution is fully resolved -4 points.