There are $n$ cities in a country, one of which is the capital. An airline operates bi-directional flights between some pairs of cities such that one can reach any city from any other city. The airline wants to close down some (possibly zero) number of flights, such that the number of flights needed to reach any particular city from the capital does not increase. Suppose that there are an odd number of ways that the airline can do this. Prove that the set of cities can be divided into two groups, such that there is no flight between two cities of the same group. Proposed by Pranjal Srivastava
Problem
Source: India IMOTC Practice Test 2 Problem 1
Tags: combinatorics, graph theory
31.05.2024 10:51
Let $v_0$ be the capital. Let $S_0:=\{v_0\}$ and $S_i, i=1,2,\dots,m$ be the set of vertices for which the shortest path from $v_0$ to each of them has length $i$. We denote by $N^{+}(S_i)$ the set of all neighbours of $S_i$ that are in $S_{i+1}$. Clearly $V=\cup_{i=0}^m S_i$ and any edge of the graph connects either two vertices in a same set $S_i$ or connects a vertex from $S_i$ and a vertex from $S_{i+1}$. Moreover $$N^{+}(S_i)=S_{i+1}\qquad (1).$$Let $U$ be a set of edges that upon removing them, the minimum path length needed to reach any particular vertex from $v_0$ does not increase. It is easy to see that after removing the edges in $U$ the condition $(1)$ still holds and vice versa - if upon removing $U$ the condition $(1)$ still holds then the statement of the problem is satisfied. We denote by $N_i, i=0,1,\dots,m-1$ the number of subsets of the edges between $S_i$ and $S_{i+1}$ such that after removing these edges, the condition $(1)$ still holds. Let $k_i,i=1,2,\dots,m$ be the number of edges that connect vertices inside $S_i$. Then the number $N$ of ways of removing edges such that $(1)$ still holds is equal to $$N= \prod_{i=1}^{m}2^{k_i}\cdot \prod_{i=1}^{m-1}N_i .$$Since $N$ is odd, we conclude $k_i=0,i=1,2,\dots,m$. This means that there are no edges inside $S_i$. Now set $A=\bigcup_{i \text{ even}} S_i$ and $B=\bigcup_{i \text{ odd}} S_i$. Clearly, there are no edges between $A$ and $B$.
31.05.2024 11:18
17.06.2024 00:37
Take cycle of odd length. It contains two adjacent vertices of equal depth. The edge between them changes nothing so for every deletion keeping it we can delete it and vice versa.
21.06.2024 18:05
Assume otherwise that there exists an odd cycle. An easy parity argument shows that there exists two adjacent vertices on this odd cycle equidistant from the capital. Then deleting or keeping the edge between them has no effect on the distance from any city to the capital. Thus the number of ways to close down flights is even, a contradiction.