In a country, there are \( n \) cities. Each pair of cities is connected either by a paved road or a dirt road. It is known that there exists a pair of cities such that it is impossible to travel between them using only paved roads. Show that, in this case, it is possible to travel between any two cities using only dirt roads.
Problem
Source:
Tags: combinatorics, Chile
31.10.2024 03:42
prety weak statement. Take an arbitrary graph $G \subseteq K_n$. Fix any four vertices $d_1, d_2, v_1, v_2$. We show that either $d_1$ and $d_2$ are connected on $G$ or $p_1$ and $p_2$ are connected on $K_n \setminus G$. FTSOC suppose that $d_1, d_2$ are disconnected and $p_1, p_2$ are disconnected suppose not. Then if the connected components of $G$ are $G = D_1 \sqcup D_2 \sqcup \dots \sqcup D_m$ where $d_1 \in D_1, d_2 \in D_2$ and likewise for $P_1 \sqcup P_2 \sqcup \dots \sqcup P_n$. Take a $m \times n$ where $(i, j)$ is filled in if $T_{ij} \coloneq D_i \cap P_j$ is empty. Since each row and column contains a filled square it follows that there exists two filled squares $(a_1, b_1), (a_2, b_2)$ which don't share a row or a column. Then there's no connections between an element of $T_{a_1b_1}$ and $T_{a_2b_2}$, contradiction due to $D_{a_1}, D_{a_2}$ and $P_{a_1}, P_{a_2}$ being disconnected.