Problem A. 888. (October 2024)
A. 888. Let \(\displaystyle n\) be a given positive integer. Find the smallest positive integer \(\displaystyle k\) for which the following statement is true: for any given simple connected graph \(\displaystyle G\) and minimal cuts \(\displaystyle V_1\), \(\displaystyle V_2\), \(\displaystyle \ldots\), \(\displaystyle V_n\), at most \(\displaystyle k\) vertices can be chosen with the property that picking any two of the chosen vertices there exists an integer \(\displaystyle 1\leq i\leq n\) such that \(\displaystyle V_i\) separates the two vertices. A partition of the vertices of \(\displaystyle G\) into two disjoint non-empty sets is called a minimal cut if the number of edges crossing the partition is minimal.
Proposed by András Imolay, Budapest
(7 pont)
Deadline expired on November 11, 2024.
We claim that \(\displaystyle k=2n\). A good example for \(\displaystyle k=2n\) is a cycle with \(\displaystyle 2n\) vertices. Let the vertices be \(\displaystyle v_1\), \(\displaystyle v_2\),..., \(\displaystyle v_{2n}\) and let \(\displaystyle V_i\) be the cut between vertices \(\displaystyle v_i\), \(\displaystyle v_{i+1}\),..., \(\displaystyle v_{i+n-1}\) and the rest of the vertices for \(\displaystyle 1\le i \le n\). Observe that these are minimal cuts since each cut contains two edges, and it's not possible to find a cut with a single edge since there is no bridge in a cycle. We also have to check that all vertices can be chosen, i.e. any two vertices can be separated with one of the \(\displaystyle V_i\)'s. Indeed, considering any two vertices, there are least \(\displaystyle n-1\) vertices between them on one the two arcs of the cycle, and thus one of the two parts of the cut can be chosen to be one of the vertices and the \(\displaystyle n-1\) subsequent vertices from the arc with at least \(\displaystyle n-1\) vertices.
Now let's prove that \(\displaystyle k\le 2n\). Let \(\displaystyle G(V,E)\) be an arbitrary graph, and the \(\displaystyle V_1\), \(\displaystyle V_2\),..., \(\displaystyle V_n\) be minimal cuts. Let's assign a 0-1 sequence to each vertex \(\displaystyle v\) of the graph in the following way: let \(\displaystyle S_1\),..., \(\displaystyle S_n\) denote one of the two parts in each cut, and let the \(\displaystyle i^{\text{th}}\) digit of the code assigned to \(\displaystyle v\) be 1 if and only if \(\displaystyle v\in S_i\). Now observe that two vertices can be separated with one of the cuts if and only if their codes are different. Thus we have to prove that there can be at most \(\displaystyle 2n\) different codes assigned to the vertices of the graph.
Let a code be called even, if there are an even number of 1's in it, otherwise let's call it odd. For any cut \(\displaystyle S\) let \(\displaystyle d(S)\) denote the number of edges connecting the two parts of \(\displaystyle S\). For every code \(\displaystyle x\) let \(\displaystyle V_x\) denote the cut between the vertices with code \(\displaystyle x\) and the rest of the vertices. Now the key is the following lemma:
Lemma.
\(\displaystyle \sum_{i=1}^n d(V_i) \geq \sum_{x \text{ is even}} d(V_x) \quad \text{ and } \quad \sum_{i=1}^n d(V_i) \geq \sum_{x \text{ is odd}} d(V_x).\)
Proof. We will only prove the first inequality, the second can be prove in a similar manner. We will show the following: we count every edge on the left hand side at least as many times as on the right hand side.
Let \(\displaystyle e\) be an arbitrary edge and let \(\displaystyle x\) and \(\displaystyle y\) denote the codes of its endpoints. There are several cases to check:
- If both \(\displaystyle x\) and \(\displaystyle y\) are odd, then \(\displaystyle e\) is not counted on the right hand side.
- If exactly one of \(\displaystyle x\) and \(\displaystyle y\) is odd, then \(\displaystyle e\) is counted once on the right hand side, and it's also counted on the left hand side, since the two codes are different, thus the vertices with codes \(\displaystyle x\) and \(\displaystyle y\) must be separated from each other in at least one of the cuts.
- If \(\displaystyle x\) and \(\displaystyle y\) are both even, and \(\displaystyle x=y\), then \(\displaystyle e\) is not counted on either side. If \(\displaystyle x\neq y\), then \(\displaystyle e\) is counted twice on the right hand side, and it's also counted at least twice on the left hand side, since \(\displaystyle x\) and \(\displaystyle y\) differ from each other at least at two places, and thus separated by at least two cuts.
Now it's easy to finish the proof: since \(\displaystyle d(V_i)\) has the smallest possible positive value (it cannot be zero since \(\displaystyle G\) is connected), thus we can have at most \(\displaystyle n\) non-zero \(\displaystyle d(V_x)\) when \(\displaystyle x\) is even. If \(\displaystyle d_(V_x)=0\), then \(\displaystyle V_x\) is partitioned into the empty set and \(\displaystyle V\) (since \(\displaystyle G\) is connected), meaning that either \(\displaystyle x\) does not appear as a code, or every vertex has code \(\displaystyle x\), the latter being impossible, since then none of the vertices would be separated by the chosen minimal cuts. Thus we can have at most \(\displaystyle n\) different even codes assigned to the vertices, and similarly, the number of odd codes assigned to the vertices is also at most \(\displaystyle n\), which concludes the proof.
Statistics:
12 students sent a solution. 7 points: Aravin Peter, Bodor Mátyás, Czanik Pál, Holló Martin, Varga Boldizsár. 6 points: Szakács Ábel. 5 points: 1 student. 1 point: 2 students. 0 point: 3 students.
Problems in Mathematics of KöMaL, October 2024