'N ' cities are connected by 'n' airlines. Prove that at least one of the airlines can offer a round trip with an odd number of landings

Question

'N ' cities are connected by 'n' airlines. There is direct non- stop service between any two cities by at least one airline and all airlines provide service in both the directions. If N>2^n, then prove that at least one of the airlines can offer a round trip with an odd number of landings. I've tried an induction method that failed.

Answer 1

Let no one of airlines cannot offer a round trip with odd length

Graph with the N vertices and edges from kth airline - Gk

Gk = Ak+Bk (where are no edges from A to A and from B to B)

Set to each vertice boolean list of length n with kth element is true where vertice in Ak

Where are only 2^n different lists => we can find vertices X and Y what which lists are equal => where are no edge from X to Y in any airline

So, it is false.

Answer 2

kotomord’s answer is right, and I’ve upvoted it, but it’s very hard to follow as written; this is an expanded version that may be a bit more accessible. I’ll be happy to delete it if he wants to copy it to replace his version.

Let $V$ be the set of $N$ cities. For $k=1,\ldots,n$ let $G_k$ be the graph with vertex set $V$ and an edge between vertices $u$ and $v$ if and only if airline $k$ has direct service between those two cities. If airline $k$ has no round trips with an odd number of landings, then every circuit in $G_k$ has even length, and $G_k$ is therefore bipartite.

Suppose that each $G_k$ is bipartite. Fix a vertex $u\in V$. For each $v\in V$ and $k=1,\ldots,n$ let

$$b_v(k)=\begin{cases} 1,&\text{if }u\text{ and }v\text{ are in the same partite set of }G_k\\ 0,&\text{otherwise}\;, \end{cases}$$

and let $b_v=\langle b_v(1),\ldots,b_v(n)\rangle$. $N>2^n$, so there are distinct $v,w\in V$ such that $b_v=b_w$. But then $v$ and $w$ are in the same partite set of $G_k$ for $k=1,\ldots,n$, and there is therefore no airline offering direct service between $v$ and $w$. Thus, there must be at least one airline $k$ such that $G_k$ is not bipartite and therefore contains a circuit of odd length.