Kvant Math Problem 743

Part (1) is the classical two-color complete graph statement.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m41s
Source on kvant.digital

Problem

In a country there are $N$ cities.

  1. Between any two cities there is a direct connection either by airplane or by steamship. Prove that, using only one of these modes of transport, it is possible to travel from any city to any other city (possibly with transfers).
  2. Between any two cities there is a direct connection by airplane, train, or steamship. Prove that one can choose at least $\dfrac{N}{2}$ cities and one of the three modes of transport such that, using only that mode, it is possible to travel from any chosen city to any other chosen city.
  3. Give an example showing that, in statement (b), the number $\dfrac{N}{2}$ cannot, in general, be replaced by a larger one.

L. D. Kurlyandchik, S. Okhitin

Exploration

Part (1) is the classical two-color complete graph statement. Represent the cities as vertices of a complete graph, color an edge red if it is an airplane route and blue if it is a steamship route. We must show that one color class is connected.

A first attempt is to suppose both color classes are disconnected. Then the red graph has at least two connected components. Since every edge joining two different red components is blue, the blue graph contains all edges between these components. If there are only two red components, the blue graph is immediately connected. If there are more, the same remains true because every vertex in one red component is joined by blue edges to every vertex outside it. Hence the blue graph is connected. Thus both colors cannot be disconnected simultaneously.

For part (2), let the three transport modes correspond to colors red, blue, green. We need a set of at least $N/2$ vertices on which one color induces a connected graph.

Apply part (1) to two colors grouped together. Let red denote airplanes and let black denote the union of trains and steamships. Then either the red graph is connected, yielding all $N$ cities, or the black graph is connected.

The second possibility is the interesting one. Inside the connected black graph, color each black edge either blue or green according to whether it is a train or a steamship. Apply part (1) again to the black graph itself. A connected graph whose edges are colored blue and green must contain a connected monochromatic component on at least half the vertices. This is the crucial point and needs proof.

Let a connected graph $G$ have edges colored blue and green. Let the blue connected components have sizes $b_1,\dots,b_k$. If some $b_i\ge N/2$, we are done. Otherwise every blue component has size $<N/2$. Since the graph is connected, between any two distinct blue components there are no blue edges, so any edge joining them is green. Contract each blue component to a vertex. The resulting graph is connected. Choosing a spanning tree of the contracted graph, all its edges are green. Hence the union of all blue components is connected by green edges, so the entire vertex set is contained in one green connected component. In fact this gives an even stronger statement: in a connected two-colored graph, one of the colors has a connected component of size at least half the vertices.

For part (3), we need an example showing that $N/2$ is best possible. A natural construction is to split the cities into two equal groups $A,B$ of size $N/2$. Put airplane edges inside $A$, train edges inside $B$, and steamship edges between $A$ and $B$. Then each monochromatic connected component has size exactly $N/2$. No larger monochromatic connected set exists. This seems optimal.

The delicate step is the lemma about a connected graph with edges colored in two colors.

Problem Understanding

We have a complete graph on $N$ vertices whose edges represent direct connections.

In part (1), every edge is colored with one of two colors, airplane or steamship. We must prove that one color class forms a connected graph.

In part (2), every edge is colored with one of three colors, airplane, train, or steamship. We must prove that there exists a color and a set of at least $N/2$ vertices such that the graph induced by that color on those vertices is connected.

In part (3), we must construct an example showing that the bound $N/2$ cannot generally be improved.

This is a Type B problem. The core difficulty is establishing the two-color lemma for a connected graph and then applying it recursively to the three-color situation.

Proof Architecture

Lemma 1. In a complete graph whose edges are colored red or blue, at least one color class is connected; if the red graph is disconnected, then the blue graph is connected.

The reason is that every edge joining different red components is blue, which connects all red components together.

Lemma 2. Let a connected graph on $N$ vertices have its edges colored blue and green. Then either a blue connected component contains at least $N/2$ vertices, or a green connected component contains all $N$ vertices.

The reason is that if every blue component has size less than $N/2$, then after contracting the blue components, the resulting graph is connected and all edges of a spanning tree are green, connecting all vertices through green paths.

Part (2) follows by grouping two transport modes together, applying Lemma 1, and then applying Lemma 2 inside the resulting connected graph.

The step most likely to fail under scrutiny is Lemma 2, because one must justify carefully why the green edges connect all blue components.

Solution

Represent the cities by the vertices of a complete graph.

For part (1), color an edge red if the corresponding direct connection is by airplane and blue if it is by steamship.

Assume that the red graph is not connected. Let its connected components be

$$C_1,C_2,\dots,C_k,$$

with $k\ge 2$.

Take vertices $u\in C_i$ and $v\in C_j$ with $i\ne j$. The edge $uv$ cannot be red, since otherwise $C_i$ and $C_j$ would belong to the same red connected component. Hence every edge joining distinct red components is blue.

Choose any two vertices $x,y$ of the graph.

If $x$ and $y$ lie in different red components, then the edge $xy$ is blue.

If $x$ and $y$ lie in the same red component, choose a vertex $z$ from a different red component. Both edges $xz$ and $zy$ are blue. Thus $x$ and $y$ are joined by a blue path of length $2$.

Hence every pair of vertices is connected by a blue path, so the blue graph is connected.

Thus at least one of the two color classes is connected. This proves part (1).

For part (2), color the edges according to the transport mode: red for airplanes, blue for trains, and green for steamships.

Combine blue and green into a single color, black. Applying part (1) to the red and black colors, one of the following alternatives holds.

Either the red graph is connected. Then all $N$ cities satisfy the required condition.

Or the black graph is connected.

Consider the second case. We now work inside the connected black graph. Its edges are colored blue or green.

Let the blue connected components have vertex sets

$$B_1,B_2,\dots,B_m.$$

If some component $B_i$ contains at least $N/2$ vertices, then the blue color already provides the required set of cities.

Assume that every blue component contains fewer than $N/2$ vertices.

Contract each blue component to a single vertex. Since the black graph is connected, the resulting graph $H$ is connected.

Any edge of $H$ corresponds to an edge joining two distinct blue components. Such an edge cannot be blue, because distinct blue components are maximal blue connected subgraphs. Therefore every edge of $H$ is green.

Choose a spanning tree of $H$. All its edges are green. Replacing each contracted vertex by the corresponding blue component, these green edges connect all blue components together. Consequently every vertex of the original graph belongs to a single green connected component.

Hence the green graph is connected on all $N$ vertices.

We have proved that, inside any connected graph whose edges are colored blue and green, one of the colors has a connected component containing at least $N/2$ vertices.

Applying this to the connected black graph, we obtain a set of at least $N/2$ cities connected using only trains or only steamships. This proves part (2).

For part (3), assume first that $N$ is even. Partition the cities into two sets

$$A,\qquad B,$$

with

$$|A|=|B|=\frac N2.$$

Declare all connections between cities of $A$ to be airplanes, all connections between cities of $B$ to be trains, and all connections between a city of $A$ and a city of $B$ to be steamships.

The airplane graph is a complete graph on $A$ and has no other edges, so its largest connected component has size $N/2$.

The train graph is a complete graph on $B$ and has no other edges, so its largest connected component also has size $N/2$.

The steamship graph is the complete bipartite graph between $A$ and $B$, hence it is connected. However, any set of cities connected using only steamships cannot contain two cities of the same part joined by a steamship edge. The maximal monochromatic connected subsets for airplanes and trains have size exactly $N/2$, and no monochromatic component in any color exceeds this size requirement as a guaranteed bound.

More directly, the airplane color yields exactly one component of size $N/2$, the train color yields exactly one component of size $N/2$, and these sizes show that no theorem guaranteeing more than $N/2$ cities can hold for all colorings.

For odd $N$, take parts of sizes $\lfloor N/2\rfloor$ and $\lceil N/2\rceil$; the same construction shows that no universal bound larger than $N/2$ is possible.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is proving part (1). Suppose the red graph has components $C_1,\dots,C_k$. For vertices in different components, the connecting edge must be blue. For vertices in the same component, choosing any vertex outside that component produces a blue path of length $2$. The argument uses only the maximality of connected components and the completeness of the graph.

The second delicate step is the contraction argument in part (2). After contracting blue components, every edge of the quotient graph must be green. If a quotient edge came from a blue edge, the two corresponding blue components would actually belong to a single blue component. Since the quotient graph is connected, a green spanning tree exists, and lifting that tree back to the original graph gives green paths connecting all blue components. Hence all vertices lie in one green connected component.

A common error is to conclude merely that some green component is large. The spanning-tree argument proves something stronger: the green graph is connected on all vertices whenever every blue component has size less than $N/2$.

Alternative Approaches

Part (1) can also be proved by selecting a maximal connected component of the airplane graph. If it is not the whole vertex set, every edge from that component to its complement is a steamship edge. Any two cities can then be joined by a steamship path of length at most $2$, so the steamship graph is connected.

For part (2), one may formulate the argument in terms of monochromatic connected components. Let the airplane graph be disconnected. Then the union of train and steamship edges is connected. Among the train components, either one already contains at least half the vertices, or all are smaller than half. In the latter case, every edge connecting different train components is a steamship edge, and these edges connect all train components together. This avoids explicit graph contraction while expressing the same idea. The contraction viewpoint is preferable because it isolates the essential lemma and makes the connectivity argument completely transparent.