Let $n\ge 3$ be an integer. In a country there are $n$ airports and $n$ airlines operating two-way flights. For each airline, there is an odd integer $m\ge 3$, and $m$ distinct airports $c_1, \dots, c_m$, where the flights offered by the airline are exactly those between the following pairs of airports: $c_1$ and $c_2$; $c_2$ and $c_3$; $\dots$ ; $c_{m-1}$ and $c_m$; $c_m$ and $c_1$. Prove that there is a closed route consisting of an odd number of flights where no two flights are operated by the same airline.
Problem
Source: Romanian Masters in Mathematics 2020, Problem 3
Tags: combinatorics, RMM, RMM 2020, graph theory
01.03.2020 13:00
Here is my solution on the contest. Represent the situation in the obvious way with a graph $G$. We induct on $n$, the base case is trivial. Select an arbitrary vertex $v$ with non-zero degree and let its neighbourhood be $u_1, u_2, \ldots u_k$. While some $u_i$ remains adjacent to $v$, perform the following operation: Select an arbitrary airline $A$ that flies from $v$ to $u_i$. Delete all edges along which $A$ flies. Merge $u_i$ with $v$ and do not alter any other edges. Let the resulting graph be $G'$. If any airline has an even number of self-loops from $v$ to $v$ take an odd cycle the airline flies along and delete all other edges. If any airline has an odd number of self loops from $v$ to $v$ then we have an edge between some $u_x$ and some $u_y$ in $G$ along which the airline flies. In all other cases, an odd rainbow cycle exists in $G'$ by induction. If this cycle does not pass through $v$ in $G'$ we are done immediately. If it does then the cycle corresponds to an odd path from some $u_x$ to some $u_y$. Assume $x \neq y$. Then we can add the deleted edges from $u_x$ to $v$ and $v$ to $u_y$ to find an odd rainbow cycle in $G$. $\blacksquare$
01.03.2020 13:01
Interpret the flights as a graph $G$. If we choose one flight from each airline, then we obtain a graph $G'$ with $n$ vertices and $n$ edges. This forces $G'$ to have a cycle; we want to show we can select the flights so that this cycle is odd. Number the airlines $1, 2, \dots, n$, and label the edges of $G$ with the corresponding numbers. Claim: Select one flight from each airline so that the number of connected components in $G'$ is minimized. Take a cycle $\mathcal C$ in the connected component $\mathcal H$ of $G'$, and consider a $k$-edge in $\mathcal C$. Then all the other $k$-edges in $G$ have endpoints in $\mathcal H$. Proof. The $k$-edges form a cycle; if some $k$-edge has an endpoint $v$ not in $\mathcal H$, then we could have selected the edge between $v$ and $\mathcal H$ and reduced the number of connected components. $\blacksquare$ Now focus in on $\mathcal H$, and perform the following modifications: Take a $k$-edge as in the claim, and add all the original $k$-edges to $\mathcal H$ in red. If necessary, delete some other non-red edges in $\mathcal H$ so that the non-red edges form a tree. Here's an example for $k = 9$. [asy][asy] size(220); defaultpen(fontsize(10pt)); pair A, B, C, D, E, F, G, H, I; A = (-1.5,0); B = (-1,2); C = (0,1); D = (1.5,1); E = (3,0); F = (4,-0.2); G = (2,-1); H = (3,2); I = (0.3,-1); draw(A--C--B^^C--D--H); draw(D--E--F^^E--G--I); draw(A--B--H--E--I, dotted+red); draw(I--A, red); dot(A); dot(B); dot(C); dot(D); dot(E); dot(F); dot(G); dot(H); dot(I); label("1", A--C, dir(130)); label("2", B--C, dir(45)); label("3", C--D, dir(90)); label("4", D--H, dir(135)); label("5", D--E, dir(70)); label("6", E--F, dir(80)); label("7", E--G, dir(315)); label("8", G--I, dir(270)); label("9", A--B, dir(150)); label("9", B--H, dir(90)); label("9", H--E, dir(0)); label("9", E--I, dir(110)); label("9", I--A, dir(240)); [/asy][/asy] Let the red edges form a cycle $c_1c_2\dots c_m$, where $m$ is odd. Let $d(u, v)$ be the distance between vertices $u$ and $v$ in $\mathcal H$ along the tree. Claim: We can find some $i$ such that $d(c_i, c_{i+1})$ is even. (Here we set $c_{m+1} = c_1$.) Proof. Root the tree, and let $x_i$ be the depth of vertex $c_i$. Then the key observation is that $d(c_i, c_j) \equiv x_i+x_j\pmod 2$. If all the distances are odd, we would have $$x_1+x_2\equiv x_2+x_3\equiv \dots \equiv x_m+x_1\equiv 1\pmod 2.$$Summing and noting $m$ odd gives $$2\sum_i x_i \equiv m\equiv 1\pmod 2,$$which is a contradiction. $\blacksquare$ Now take $i$ with $d(c_i, c_{i+1})$ even, and add the red edge $c_ic_{i+1}$ to form an odd cycle with distinct labels. This is the desired construction.
01.03.2020 13:01
(soln with Anant) Pick a forest with the minimum number of components, such that no airline has more than one route as part of this forest (such a thing exists because isolated $n$ vertices is one such forest). Fix a 2-colouring scheme on the forest. Pick an unused airline $X$ ($\le n-1$ edges in forest so possible). Then look at the cycle to which it's routes belong, say $C$. By minimality of number of components, $C$ is stuck in a component of the forest (a tree). Since $C$ has an odd number of edges, some edge $Y$ connects vertices of the same colour. Mark $Y$. Observe that the tree (in which $C$ is stuck) + $Y$ is not bipartite. Hence, there is an odd cycle. We're done since no airline had more than one edge drawn.
01.03.2020 13:04
redacted
01.03.2020 14:03
We will let $\mathfrak G$ be the obvious multigraph on $n$ vertices which has $n$ odd cycles each colored with a different color; we call these given cycles the colored cycles. Our goal is to produce an odd cycle with all edges of different colors. Claim: If $\mathfrak G$ does not have a proper subgraph with fewer vertices satisfying the problem conditions, then exists a way to pick one edge of every color which give a simple graph $G$ (i.e.\ no repeated edges). Proof. By Hall's marriage lemma, in which we try to match colors to edges. Assume that there is no such $G$. Then by Hall's marriage lemma, there must exist a set $k$ colored cycles, inducing a sub-multi-graph $\mathfrak H$ of $\mathfrak G$ having fewer than $k-1$ edges. Since each connected component of $\mathfrak H$ has at least one cycle, $\mathfrak H$ has at most $k-1$ vertices. As $k \le n$, we're done. $\blacksquare$ Thus by induction on $n \ge 3$, we can assume there exists $G$ as above. If $G$ has any odd cycles, we are already done. So we assume that $G$ is bipartite, and color its vertices black and white. [asy][asy] pair A = dir(150); pair B = dir(90); pair C = dir(30); pair D = dir(-30); pair E = dir(-90); pair F = dir(210); pair G = F+dir(160); pair H = G+dir(230); pair I = D+dir(-40); transform t = scale(0.8)*shift(4,0)*rotate(-20); pair W = t*dir(45); pair X = t*dir(135); pair Y = t*dir(225); pair Z = t*dir(315); pair V = W+dir(-30); real r = 0.1; pen vtx = blue+1; draw(I--D, grey); draw(A--B, black); draw(B--C, red); draw(C--D, green); draw(D--E, blue); draw(E--F, orange); draw(F--A, palered); draw(F--G, purple); draw(G--H, mediumcyan); draw(V--W, brown); draw(W--X, deepgreen); draw(X--Y, pink); draw(Y--Z, deepcyan); draw(Z--W, lightblue); filldraw(circle(A,r), grey, vtx); filldraw(circle(B,r), white, vtx); filldraw(circle(C,r), grey, vtx); filldraw(circle(D,r), white, vtx); filldraw(circle(E,r), grey, vtx); filldraw(circle(F,r), white, vtx); filldraw(circle(G,r), grey, vtx); filldraw(circle(H,r), white, vtx); filldraw(circle(I,r), white, vtx); filldraw(circle(V,r), grey, vtx); filldraw(circle(W,r), white, vtx); filldraw(circle(X,r), grey, vtx); filldraw(circle(Y,r), white, vtx); filldraw(circle(Z,r), grey, vtx); [/asy][/asy] Since $G$ has the same number of edges as vertices, it must have some simple even cycle $\mathcal C$. Take any edge $e$ in $\mathcal C$ and look at the colored cycle containing $e$. The colored cycle is odd, so there must be some edge $e'$ of the same color as $e$ which joins two black vertices (say). Delete $e$ (which does not change the components of $G$) and add $e'$ instead. If $e'$ joined two connected components of $G-e$, then the number of connected components of $G$ has decreased. Restart the procedure with the new $G$, which is still bipartite. Otherwise, $e'$ creates a cycle, and this cycle has odd length (because of the black-white coloring) so we are done.
01.03.2020 19:44
RMM definitely loves cycles Let us first rewrite the problem condition in graph terms: Quote: Suppose that $G$ is a $n$-vertex graph. There are $n$ odd cycles $c_1, \cdots, c_n$, each colored with one of $1,2, \cdots, n$. Then there is a odd cycle $C$ such that each edge of the cycle has different colors. Now let us choose an edge $e_i$ from each $c_i$s. Then there are $n$ selected edges, and make a graph $H$ of them. $H$ may have lots of connected components, thus we will choose the one with minimum number of components among the $\prod_{i=1}^{n} |c_i|$ possible graphs. Now let its connected components be $H_1, H_2, \cdots, H_k$, but we have $n>n-k=\sum_{i=1}^{k} (|H_i|-1)$ edges, so some component must contain a cycle. Call such component $H_i$, and choose a edge $e_j$ of the cycle. Now here's the main observation: Claim: The vertices of the cycle $c_j$ are contained in $H_i$. Proof. Write $c_j=v_1v_2 \cdots v_s$, and let $e_j=v_1v_2$. If $v_3 \not\in V(H_i)$, then consider $H_i'=H_i-e_j \cup \{v_2,v_3\}$. Then the number of connected components decrease by $1$, which is impossible. Hence $v_3 \in V(H_i)$. Now we work on $H_i'$. Note that $H_i-e_j$ is connected, thus there is a path from $v_2$ to $v_3$ using these edges. These edges, together with $\{v_2,v_3\}$, form a new cycle containing $\{v_2, v_3\}$. Now apply the same method to $v_4, v_5, \cdots$ to get $v_t \in V(H_i)$ for every $t$. $\square$ Let $T$ be a spanning tree of $H_i-e_j$. It is well-known that all trees are bipartite, so let us color vertices in red and blue in alternating order. Then, since $c_i$ is an odd cycle, there must exist an edge $e$ such that its endpoints have the same color. Add such $e$ on $H_i-e_j$, then the even-length path on $T$ and $e$ forms an odd cycle. Thus we are done.
02.03.2020 01:26
Interpret the country as a graph and the airlines as different colored cycles. We will proceed with strong induction on $n$, where the base case $n=3$ is trivial. Note that, if there exist $k$ vertices in the graph such that the edges incident on them have at most $k$ colors, then we can delete these $k$ colors and vertices and finish by inductive hypothesis. Thus, suppose that each group of $k$ vertices has more than $k$ colors. Now, we will inductively construct a spanning tree with no two edges of the same color as follows: We start with two vertices connected by an edge. Then, at the stage in which we have $k$ vertices, choose a color that connects to at least one of the vertices, and has not been chosen before (this is possible since we have only chosen $k-1$ colors, and by assumption, there are more than $k$.) Consider the cycle of this color. If the cycle has a point outside the chosen $k$ vertices, then add an edge on the cycle which has exactly one endpoint among the $k$ vertices. If it is entirely in the $k$ vertices, we claim that we already win. Consider the unique paths between adjacent vertices of the cycle, which use edges from only the tree. The xor of all these paths is the empty set, so the sum of their lengths is even. As there is an odd number of such paths, there exists one of even length, and considering this path with the two vertices it connects produces an odd cycle on different colors, as desired. In this way, we will either win beforehand or find a spanning tree on $n-1$ colors. Consider this spanning tree and the cycle determined by the last color. We can use the same finish as above, so we are done.
02.03.2020 02:36
Here is a generalization: Let $|V| = n$ be a set of vertices and let $C_1,\ldots, C_n$ be cycles on $n$. Suppose furthermore that for any subset $C_{i_1}, \ldots, C_{i_k}$ of the cycles, they hit strictly more than $k$ vertices (so that the problem is not reducible). Then, if $C_n$ is an odd cycle, then we can select an odd cycle with edges in distinct $C_i$'s.
02.03.2020 03:23
Does this work? We assume that there does not exist k cycles that exist only on <=k vertices. Induction Hypothesis: Given n vertices, n-1 connected graphs that live on these n vertices s.t. no k of these graphs only live on <=k vertices, then we can choose 1 edge per color s.t. they form a spanning tree. At each step of the way, we want to choose an edge from an unused graph and fuse their vertices s.t. the hypothesis holds. Look at $G_1$ and the edges are $e_1,...,e_r$. Suppose no matter what edge we choose from $G_1$, the hypothesis breaks, let $S_i$ be the offending set if we fuse $e_i$. Then through some mildly bloody calculations we can get that $\{G_1\}US_1US_2U...US_r$ is actually an offending set in the original graph. To illustrate, if $\{G_1\},S_1,...,S_r$ were disjoint, then the number of vertices they span is at most $r+1+\sum_{i=1}^r (|S_i|+1-2) = 1+\sum_{i=1}^r |S_i|$ since by the hypothesis, the graphs in $S_i$ live in at least $|S_i|+1$ vertices and in fact they should live in exactly $|S_i|+1$ vertices. If they did intersect, then the vertices must also intersect a lot, so it sure feels a lot like that the number of vertices is less than the number of sets. Thats where the calculations get a little messy. Also if $G_1$ was in $S_i$, then $S_i$ would actually be offending itself. My main concern is that given the hypothesis, a spanning tree must exist which isnt shown in the other solutions.
10.03.2020 20:40
Lemma 1. Let $ T$ be a tree, $ v_1,v_2,\dots, v_{k}$ be distinct vertices of $ T$ and $ k$ is odd. We add the edges $ v_i v_{i+1}, i=1,2,\dots,k; v_{k+1}\equiv v_1$. Then there exists an odd cycle, all its edges except one belong to $ T$. Proof. Take a root vertex $ v_0\in V(T)$ and let $ d_i,i=1,2,\dots,k$ be the distance (number of edges) from $ v_0$ to $ v_i$. Since $ k$ is odd, there exist two consecutive numbers $ d_i,d_{i+1}$ with equal parity in the circular sequence $ d_1,d_2,\dots,d_k,d_1$. Then $ v_i,\dots,u_0,\dots, v_{i+1},v_i$ is an odd cycle which contains only one edge ($ v_i v_{i+1}$) not in $ T$. Here $ u_0$ is the last vertex common to both paths $ v_0,\dots,v_i$ and $ v_0,\dots,v_{i+1}$. $ \blacksquare$ Call a configuration of $ n$ airports and $ \ell$ airlines admissible if it satisfies the requirements of the problem and $ \ell\ge n$. At the beginning we start from the original admissible configuration $ G$ of $ n$ airports and $ \ell=n$ companies. The spanning process. Take two airports and a flight between them and it be the configuration $ G_0$ with $ 2$ airports and $ 1$ flight. Suppose we are at a configuration $ G_i$ with $ k<n$ airports and $ k-1$ flights of distinct companies, making the airports connected. Take a company among those $ \ell-(k-1)$ companies, not operating on $ G_i$ . In case it operates inside the airports of $ G_i$ , we stop the process. If there exists a flight by this company connecting an airport of $ G_i$ with an airport outside $ G_i$ we add this flight and the airport to $ G_i$ and obtain the next configuration $ G_{i+1}$. Suppose now, all those $ \ell-(k-1)$ companies operate flights outside the airports in $ G_i$. So, we have admissible configuration $ G'$ of $ n-k$ airports and the flights of the $ \ell-k+1$ companies. We start the process on $ G'$. Thus, after the process has ended, we have a tree $ T$ of flights of distinct companies and an odd cycle route on the vertices of $ T$, operated by some other company. Applying Lemma 1, we are done. Remark. I posted some additional motivation on my blog.
11.03.2020 00:13
Represent this situation as a multigraph $G$ with $n$ vertices and $n$ odd cycles $c_1,c_2,...,c_n$ whose edges have different colors. We are going to obtain a large tree whose edges have different colors. Suppose at some point we have such a tree $T$ with $k+1$ vertices and $k$ edges Consider those $n-k$ cycles among those that don't contain an edge of $T$. -If such a cycle contains an edge between $T$ and $G-T$ : enlarge the tree -If all $n-k$ cycles are entirely contained in $G-T$: $(|G-T|=n-k-1) $induct on $n$ -If a cycle $c$ is entirely contained in $T$. Color the vertices of $T$ black and white such that no two vertices of the same color are adjacent in $T$. There is an edge $e$ from $c$ between two vertices of the same color. $T$ with edge $c$ contains an odd cycle all whose edges belong to different cycles. If we reach at a point where we have a tree with $n$ edges and $n-1$ edges we are done.
24.05.2020 13:01
We proceed by strong induction on \(n\), with base case trivial. Let the vertex set be \(V\). We will try to construct a spanning tree on the \(n\) vertices, where each edge is a distinct color. This will not always be possible, but when it is impossible, we will be able to induct down. Begin by selecting an edge (i.e.\ tree with two vertices) \(v_1\sim v_2\). We iteratively add vertices to our tree. Say at some step in the process, we have a tree on the vertices \(v_1\), \(\ldots\), \(v_k\), with \(k<n\), and that the \(k-1\) edges cover \(k-1\) distinct colors. There are three cases from here: We can find another color whose cycle contains some vertex in \(\{v_1,\ldots,v_k\}\), but also contains some vertex in \(V\setminus\{v_1,\ldots,v_k\}\). Then there is an edge of this color of the form \(v_i\sim w\), where \(w\notin\{v_1,\ldots,v_k\}\). Add this vertex \(w\) to the tree. We can find another color whose cycle is contained entirely in \(\{v_1,\ldots,v_k\}\). Then there are \(k\) cycles on the subgraph with vertices \(\{v_1,\ldots,v_k\}\), so we win by the inductive hypothesis. No other colors have cycles that contain an element of \(\{v_1,\ldots,v_k\}\). In the subgraph consisting of the remaining \(n-k\) vertices, there are \(n-k\) cycles, so we win by the inductive hypothesis. If at any point in the process, one of conditions (ii), (iii) holds, then we are already done. Otherwise, we successfully construct a spanning tree with \(n-1\) edges of distinct colors. Let \(x_1\sim x_2\sim\cdots\sim x_m\sim x_1\), with \(m\) odd, be the cycle formed by the remaining color, and consider the paths from \(x_1\) to \(x_2\), from \(x_2\) to \(x_3\), \ldots, from \(x_m\) to \(x_1\) in the spanning tree. The sum of their lengths must be even, so one of them, say the path from \(x_i\) to \(x_{i+1}\) (indices modulo \(m\)), has even length. Then union this path with the edge \(x_i\sim x_{i+1}\) to construct a cycle of odd size all of whose edges are distinct colors. End proof.
10.03.2021 10:59
Consider a collection $n$ odd cycles, they are bot necessarily distinct. All are on the same vertex set of size $n$. Proof- Call a set of the edges rainbow if it is formed by taking at most one edge from each cycle. By taking a maximal rainbow forest $F,$ an acyclic set of edges. Since $F$ is acyclic its size $< n$, there is a cycle $c$ in the original list has no edge of which lies on $F$. $F$ contains every vertex of $c$, otherwise an edge of $c$inside of a vertex could be added to $F$ from a larger rainbow forest, contradiction with maximality. No edge of $c$ joins with the different components of $F$. The vertices of $c$ all lie on some components of $F$. Since $c$ is an odd cycle, has an edge with endpoints both lie in the same part. This edge and the edge of the tree completes an odd rainbow cycle.
04.04.2022 15:28
We prove a claim first .Define a rainbow tree to be a tree with edges of different colours. Claim-If a colour distinct from the colours of a rainbow tree form an odd cycle within it,then we can find an odd rainbow cycle. Proof-Consider the cycle to be $x_1 x_2 ...x_{2k+1}$.Define $d(v_1,v_2)$ to be the number of vertices between $v_1,v_2$,including $v_1$ but excluding $v_2$,in the shortest path between these two vertices on the tree(just the number of edges in the path).Also $d(v,v)=0$. Assuming contrary,we have $d(x_i,x_{i+1})$ is odd. We prove by induction that $d(x_1,x_{2m})$ is odd and $d(x_1,x_{2m+1})$ is even. We prove the latter ,proof of the former is the similar. Assume we have $x_1,x_{2m},x_{2m+1}$,such that $d(x_1,x_{2m})$ is odd.If $x_1,x_{2m},x_{2m+1}$ lie on a path on the tree,then the result is immediate as $d(x_1,x_{2m+1})=+-d(x_1,x_{2m})+-d(x_{2m},x_{2m+1})$ Otherwise consider the skeleton of the tree and let the point of attachment of the branches of $x_1,x_{2m},x_{2m+1}$ be $v_1,v_{2m},v_{2m+1}$. By assumption we get $d(x_1,v_1)+d(v_1,v_{2m})+d(v_{2m},x_{2m}) \equiv 1 \pmod 2$ and $d(x_{2m},v_{2m})+d(v_{2m},v_{2m+1})+d(v_{2m+1},x_{2m+1}) \equiv 1 \pmod 2$. So we get $d(x_1,v_1)+d(v_1,v_{2m})+d(v_{2m},v_{2m+1})+d(v_{2m+1},x_{2m+1}) \equiv 0 \pmod 2$. Now using that $d(v_1,v_{2m+1})=+-d(v_1,v_{2m})+-d(v_{2m},v_{2m+1})$.,we get that $d(x_1,x_{2m+1})$ is even.This completes the induction. So $d(x_1,x_{2k+1})$ is even and using the rainbow tree,we get our odd rainbow cycle. We can also assume the graph to be connected.Consider the connected components.Any colour must be completely contained inside a component.By pigeonhole,we get a component,such that the number of colours in it is atleast its size.We can now induct.Hence ,we can now assume connected. Now,in our graph,we generate a rainbow tree.Start with an arbitrary vertex and add an unadded vertex to the tree ,such that it was connected with the tree with an unused colour(in the tree). If we stop at some point,then there are two possibilities. _All colours passing through the tree vertices are already the edges of the tree.We can induct on $G$\tree. _Otherwise,consider a colour $c$ through a vertex of the tree not already present as an edge in the tree. Now,lookin at its cycle ,if it is not entirely contained in the tree,then we get verticees $v_1,v_2$,such that these vertices are connected with an edge of colour $c$,and vertex $v_1$ on the tree and $v_2$ outside,wherein we can continue the process. If it is entirely contained,we can use the claim above and finish. If the algorithm terminates, as the graph is connected and we don't create cycles(we add vertices not in the tree),we end up with a rainbow spanning tree.This has $n-1$ colours used only,so we can still apply the claim and finish.
08.01.2023 02:55
Call a cycle with no two edges of the same color rainbow. Generate good subgraphs by selecting one edge per airline. We consider a good subgraph $G$ with minimum number of connected components. There are $n$ edges in the subgraph. Thus, there is a rainbow cycle. Let graph $F$ be a spanning forest of the good subgraph that contains all edges in the rainbow cycle except for one. Let the last vertex be part of the airline $\kappa$. Denote the cycle formed by airline $\kappa$ as the $\kappa$-cycle. Claim: The vertices of the $\kappa$-cycle are all contained in the same tree $T$ of $F$. Proof: Had a vertex been outside of $F$, there must be an edge of the rainbow cycle connecting two separate trees. Replacing the original selection of $\kappa$'s edge with the edge in consideration, we obtain a good subgraph with one fewer connected component, contradicting minimality of $F$. $\square$ Label the vertices of $T$ with $0$ and $1$ in bipartite fashion. The $\kappa$-cycle must contain two adjacent vertices with the same label, as it has odd length. The union of this edge of the $\kappa$-cycle and the unique path between the two vertices in $T$ generates a rainbow odd cycle, as desired.
26.02.2023 23:44
Fun problem Take the obvious graph theoretic interpretation. Pick an edge from each of the airlines' cycles; we now get a subgraph with $n$ edges and $n$ vertices, so a cycle must exist. If the cycle is odd, we are already done. Otherwise, the connected component with the cycle $C_1C_2...C_{2t}$ must be bipartite, with a unique bipartition based on graph theoretic distance from some vertex $V$. It is easy to see that removing the edge $C_1C_2$ does not change the bipartition of the component or its connectedness. However, let $i$ be the airline of that deleted edge; as $i$'s edges are an odd cycle, there exists some edge of $i$ that either: Violates the bipartition of the component, and hence can be added to cause an odd cycle and solve the problem Connects this component to some other connected component In either case, add the desired edge. Then, either the problem is solved, or the number of connected components decreases by $1$. As the latter cannot happen more than $n-1$ times, the problem is eventually solved. Q.E.D. Note: In theory, this can be a multigraph instead; however, everything still is robust if a double edge is counted as a 2-cycle.
14.03.2023 00:29
Amazing problem Label all vertices with 0 or 1 at the start. Consider the following process to generate a subgraph: on step $1\le i\le n$, include any edge of color $i$ between two vertices with the same label, which must exist as odd cycles aren't bipartite. Then, if it joins two connected components, flip all labels of either one. Clearly the label is a 2-coloring of some spanning forest at any given time. Since the resulting subgraph has $n$ edges, at some point, we must have drawn an edge between two vertices in the same connected component, which induces an odd cycle.
11.12.2023 05:06
The main claim is that we can chose a set of $n$ edges each of different airline such that no two edges are between the same airports. By halls-marriage theorem, this is the case iff for every subset of size $k$ of airlines the union of there edges has size at least $k$. If not, consider the smallest subset of $k$ airlines such that the union is less than $k$, say size $s$. If we take the edge between $v_1, v_2$ that contains the most shared airlines say set $T$ by PHP it has at least 4 elements, which is plenty. Consider the triangles formed by $v_1, v_2$ to any vertex $v$ using an edge in $T$. We can choose a rainbow triangle such that at least one of $(v_1, v)$ and $(v_2, v)$ contains an element from the same airline as in $T$, as long as not all of the pairs of edge sets between $(v_1, v), (v_2, v)$ are singletons with elements $a_1, a_1$ where $a_1 \in T$. If this were the case, however we can consider the subgraph subtracting these airlines and induct down to satisfy the claim. Now we have $n$ edges and thus at least 1 cycle in the rainbow subgraph. If any cycle is odd, we are done. Otherwise we have a bipartite graph with minimal even cycle $C$. Consider an edge between $v_0, v_{2i+1}$ in the cycle (an odd amount apart on both sides). Unless all of the routes go to other elements in the rainbow subgraph out of $C$ this edge means one of the two cycles gives us our desired rainbow cycle. If all of the routes in $C$ leave to other vertices, then we can simply induct down $n$ and treat the cycle as a single vertex. $\blacksquare$.
25.02.2024 22:39
Start with an empty forest. Now repeatedly perform the following: Pick a color not already in the forest. If the cycle of that color is not entirely contained in a tree, then add in an edge from the cycle between different trees. Since there are $n$ cycles, eventually we will reach a cycle which is entirely contained within some tree $T$ in the forest. Now, for an edge $e$ of the cycle, if we let $f(e)$ denote the distance between the endpoints of $e$ in $T$, then $\sum f(e)$ should be even. In particular, $f(e)$ is even for some $e$, so $e$ along with the path in $T$ between its endpoints is an odd cycle with edges of all different colors as desired.
27.02.2024 21:55
Doing this problem was like a 20 hour long air plane flight. The base case $n = 3$ holds. WLOG suppose that every airport has more than one airline through it, else delete that airport and the corresponding airline. Claim: We can choose a set of $n$ distinct edges, one from each airline. Proof. Consider the bipartite map from cycles to edges. Suppose that there are $n-1$ edges that contain $n$ odd cycles. This is evidently impossible for $n \le 3$. If $n \ge 3$, then we can induct downward to get an odd cycle and finish. Else, Hall's condition is satisfied and we get the desired set. $\blacksquare$ We can get $n$ distinct edges, which gives us a rainbow cycle of length $\ge 4$. Now $2$-color the rainbow cycle, red and blue. If there are any red to red or blue to blue edges, we are done by choosing an odd cycle. Let $\mathcal{C}$ be the set of colored cycles use to create this cycle. It follows that none of $\mathcal{C}$ is contained solely in the cycle. Now, replace the rainbow even cycle with a $r$ and $b$ vertex, and for each cycle replace its occurences in the cycle with just one connection between $r$ and $b$ each time. The cycles can be made simple. Induction finishes.