There are two countries A and B, where each countries have n(≥2) airports. There are some two-way flights among airports of A and B, so that each airport has exactly 3 flights. There might be multiple flights among two airports; and there are no flights among airports of the same country. A travel agency wants to plan an exotic traveling course which travels through all 2n airports exactly once, and returns to the initial airport. If N denotes the number of all exotic traveling courses, then prove that N4n is an even integer. (Here, note that two exotic traveling courses are different if their starting place are different.)
Problem
Source: Korea National Olympiad 2nd Round 2019 #8
Tags: combinatorics, graph theory, hamiltonian cycle, matching
16.11.2019 13:59
Half of the 2019 KMO's afternoon problems are well known by past winter school education (MOP of South Korea) #7 : Easier version of 2014 Winter School practice test problem #8 : Graph theory results already written as a paper
16.11.2019 14:04
EagleEye wrote: Half of the 2019 KMO's afternoon problems are well known by past winter school education (MOP of South Korea) #7 : From 2014 Winter School practice test #8 : From home education after 2012 Winter School and maybe #8 is just a famous graph theory exercise Wow, that's so disappointing. There were some contestants aware of #7(including me), but I've thought that #8 was new...
16.11.2019 14:56
Wrong solution
I got new correct solution by induction on n but it's too hard to write solution without many figures... Basic idea is the following If there's a multi edge, it is quite obvious. If G is a simple graph, use induction on n. n=2 is impossible. K_{3,3} is the only case when n=3 and it has 6 distinct hamiltonian cycles. Let a_1 b_1 be a edge in G, a_1 \in A, b_1 \in B. The adjacent vertices of a_1 are b_1 ,b_2 ,b_3 \in B and the adjacent vertices of b_1 are a_1 ,a_2 ,a_3 \in A Let G' be the graph obtained by removing two vertices a_1 , b_1 from G and connecting a_2 b_2 , a_3 b_3 with edges. Also define G'' be the graph obtained by connecting a_2 b_3 , a_3 b_2 instead. Use the induction hypothesis on G', G''. And try to convert hamiltonian cycles of G' or G'' to hamiltonian cycles of G. Then we may consider the followings. (1) Hamiltonian cycles of G' or G'' which cannot be converted to hamiltonian cycles of G (2) Hamiltonian cycles of G which is counted more than once when we add the number of hamiltonian cycles of G' and that of G''. By some case works it is possible to define a converting process which satisfies (1) Hamiltonian cycles of G' which cannot be converted to hamiltonian cycles of G is 1-1 matched to those of G'' (2) There's no duplication. It can be easily seen that this shows the induction step.
21.11.2019 05:18
I proved it to count the number of set \left\{A,B,C\right\} where \left\{A,B,C\right\} are partition of edges and each one is perfect matching
21.11.2019 06:16
Here is my full proof We call H which is a subgraph of G a d-subgraph of G when every vertices have degree d in H. Define P(G) be a set of partitions of edges of G to three perfect matchings. First, we can show that above problem is equivalent to which \left|P(G)\right| is even. (For {X,Y,Z}\in P(G), X\cup Y,Y\cup Z,Z\cup X are 2-sub graph. On the other hand, Hamiltonian cycles have unique partition to perfect matchings. But the other 2-subgraphs have even partition to perfect matchings) We show \left|P(G)\right| is even by induction on n. Take a edge a_1 b_1. And b_1,b_2,b_3 are adjacent vertices of a_1. Similarly, define a_1,a_2,a_3. P(G)=P_1\cup P_2 where P_1 is a set of partitions to perfect matching which edges a_1b_2,a_2b_1 are contained in same matching and P_2 is a set of partitions to perfect matching which edges a_1b_2,a_3b_1 are contained in same matching. Make a copy of G and remove a_1,b_1 from it and add edges a_2b_2,a_3b_3. We denoted it G_1. Make a copy of G and remove a_1,b_1 from it and add edges a_2b_3,a_3b_2. We denoted it G_2. Then there are canonical embedding f:P_1\to P(G_1) and g:P_2\to P(G_2). And there is a bijection between P(G_1)-f(P_1) and P(G_2)-g(P_2) (convert a_2b_2, a_3b_3 to a_2b_3, a_3b_2) Then, \left|P(G)\right|=\left|P(G_1)\right|+\left|P(G_2)\right|-2\left|P(G_1)-f(P_1)\right| is even.
21.11.2019 06:34
Here is more details f is the function which converts a_1b_2,a_2b_1 to a_2b_2 and a_1b_3,a_3b_1 to a_3b_3 in perfect matchings of P_1. g is the function which converts a_1b_2,a_3b_1 to a_3b_2 and a_1b_3,a_2b_1 to a_2b_3 in perfect matchings of P_2. Then, P(G_1)-f(P_1) is a set of partitions to perfect matching in G_1 which a_2b_2,a_3b_3 are contained in same perfect matching. Convert a_2b_2,a_3b_3 to a_2b_3,a_3b_2, it becomes P(G_2)-g(P_2).
24.11.2019 15:53
I have a completely different proof. Suppose that we are trying to count the number of hamiltonian cycles of a 3-regular bipartite graph G=(A\cup B,E). Fix a vertex u\in A. Call a subgraph H of G a good subgraph if all vertices in B have degree 2 in H. Given a good subgraph H, we shall color each vertex of A in red or blue, and call a coloring feasible if u is red and any two vertices in the same connected component have the same color. Let M denote the number of pair (a good subgraph, a feasible coloring). If we fix a good subgraph H, then there are 2^{\text{number of components of }H-1} ways to make a feasible coloring. In particular, M has the same parity with the number of connected good subgraphs. Conversely, fix a coloring, i.e. suppose that we color vertices of A where u is red. Then, the number of such coloring is 2^{n-1}, in particular, even. For each vertex b in B, there are either 3 or 1 ways of choosing two edges incident with b, so that the two edges are incident with the same color vertices in A. In particular, M is even. Therefore, it is enough to show that the number of connected good subgraphs has the same parity with the number of hamiltonian cycles, i.e. the number of connected good subgraphs that are not hamiltonian cycles is even. Now, a connected good subgraph (or any connected component in a good subgraph) has the same number of edges and the number of vertices, so that it looks like a single cycles plus some trees attached to it. Note that there are exactly two ways to assign a direction on each edge so that every vertex has out degree 1: edges in the attached trees should point toward the cycle and there are two ways to orient the cycle. Fix a cycle C of G that uses k<n vertices from each of A,B. We shall prove that there are even number of ways to select some of the remaining edges to make a connected good subgraph. First, fix an orientation C. Then, take the n-k vertices of A not in C. Take any perfect matching to the n-k vertices of B not in C and direct those edges from vertices in A to vertices in B. Then, from each of the n-k vertices in B, choose any edge between the two edges that has not been used. We have 2^{n-k} choices, in particular, even number of choices. Now, this procedure produces a good subgraph (which may not be connected) that contains C (with a fixed orientation) and each edge is given an orientation so that all outdegrees are 1. Also, this procedure produces all such pairs (good subgraph containing C, orientation), so that the number of such pairs is even. However, if we have a good subgraph containing C (with a fixed orientation), then there are 2^{\text{number of components}-1} ways to orient the edges because we have two choices for each connected components except for the component of C (because we already have fixed an orientation). The number of pairs (good subgraph containng C, orientation) has the same parity with the number of connected good subgraph contaning C, and the number of such pairs is even as we have already observed.
25.11.2019 00:19
26.11.2019 14:54
I would give proof by induction without relation with perfect matching. This can be seen as somewhat correct version of @EagleEye's. In order to avoid proof full of word 'Hamiltonian cycle's, I will used 'H-cycle' instead. <Sketch of the Proof> Let H(G) be the number of H-cycles in the graph G. We will prove by induction on n. When the given graph is not simple, you can easily verify that the number is even. If simple, select any connected two points x, y. Denote x_1, x_2, y_1, y_2 be the other points connected to y and x each. Our goal is deleting x, y and find correspondence between H-cycles in 'reduced graphs' and the original graph G.This can easily done by handling cases. <Proof> The first step is defining the 'reduced graphs'. Let G_1 as the graph attained by deleting x,y and adding edge x_1 - y_1 and x_2 - y_2 and G_2 adding edge x_1 - y_2 and x_2 - y_1. To make new edges distinct with edges already exists, color them in blue. The Next step is carefully handling cases and finding the correspondence. A) Given H-cycle does not contain edge x-y. 1) - x_1 - x - x_2 ... - y_1 - y - y_2- This corresponds to the H-cycle with both blue edge x_1 - y_1 and blue x_2 - y_2 used in G_1. 2) -x_1 - x - x_2 ... - y_2 - y - y_1- This corresponds to the H-cycle with both blue edge x_1 - y_2 and blue x_2 - y_1 used in G_2. B) Given H-cycle contain edge x-y. 1) -y_2 - x - y - x_2- This corresponds to the H-cycle with blue x_2 - y_2 used and blue x_1 - y_1 not used in G_1 2) -y_1 - x - y - x_1- This corresponds to the H-cycle with blue x_1 - y_1 used and blue x_2 - y_2 not used in G_1 3) -y_2 - x - y - x_1- This corresponds to the H-cycle with blue x_1 - y_2 used and blue x_2 - y_1 not used in G_2 4) -y_1 - x - y - x_2- This corresponds to the H-cycle with blue x_2 - y_1 used and blue x_1 - y_2 not used in G_2 Therefore, H(G) equals to H(G_1)+H(G_2) - number of H-cycle in G_1 that does not contains any of blue edges - number of H-cycles in G_2 that does not contains any of blue edges. You can easily see that we are precisely subtracting the same value because each are H-cycles in G_1 - blue edges and G_2 - blue edges which are actually the same graph. Since H(G_1) and H(G_2) are even by the induction hypothesis, H(G) is again even.
29.12.2019 19:56
Pathological wrote: It's easy to see that every vertex in this graph has odd degree. If n_1\cup n_2=m_1\cup m_2 forms a hamiltion cycle, then (m_1,m_2,m_3) has degree zero.
03.01.2020 15:14
Not a solution; just an observation Observe by thm 1 of the attached pdf, the number of Hamiltonian cycles containing a particular edge is even. Combining this with the problem, we see that for every pair of adjacent edges, there are an even number of hamilton cycles that pass through both of these edges.
Attachments:
handshake.pdf (58kb)
18.02.2020 09:38
What does Pathological mean when he says two unordered triples of perfect matchings (m_1,m_2,m_3) and (n_1,n_2,n_3) are connected?
19.02.2020 09:48
A and B each have 2 airports x_1, x_2, y_1,y_2 respectively. Hence, C_1=x_1\to y_1\to x_2\to y_1\to x_1 C_2=x_1\to y_2\to x_2\to y_1\to x_1. C_1 and C_2 are same because their starting point is x_1. In a bipartite graph country A has 6 points a_1,a_2,a_3; u_1,u_2,u_3 Country B has also 6 points b_1,b_2,b_3; \nu_1,\nu_2,\nu_3. Each a_i connects to every b_j \deg(a_i)=3=\deg (b_j). Each b_i connects to every \nu_j ;\deg(u_i)=3=\deg(\nu_j) Note, 1\le i, j\le 3. The graph satisfies the conditions, and it doesn't consist any Hamiltonian path, so doesn't consist Hamiltonian cycle also. Number of Hamiltonian cycle=0, it is even number.
21.02.2020 15:51
If there is a concrete sequence \mathbb C, which consists all the 2n points, also forms a Hamiltonian cycle\implies \nu_1--\nu_2--\hdots\nu_{2n}(--\nu_1). In anticlockwise direction we have 2n Hamiltonian cycles. 1^{\text {st}} edge of the the cycle C'_1:\nu_1\to\nu_{2n},C'_2:\nu_{2n}\to\nu (2n-1),\hdots,C'_{2n}:\nu_2\to\nu_1 This sequence provides 2n+2n=4n no of Hamiltonian cycles. \text {Number of total Hamiltonian cycles}=N=\text {number of different C like sequences}\implies \frac {N}{4n}=\text {number of different C like sequences}=\textbf{an integer.} In some cases N maybe 0.
23.03.2020 14:55
I heard this was one of the highest combination problem's in KMO past years.
10.02.2021 18:16
This problem was reposted recently, then a guy provided this link, so it was my pleasure to see various solutions and comments on this nice problem. It boils down to prove that any simple regular bipartite graph of degree 3 has an even number of Hamiltonian cycles. This is a result of J. Bosak. Some references, comments, and a proof taken from Berge's book "Graphs and Hypergraphs", which I believe is the original one, can be found in my blog. The idea in #5 (@EagleEye), #7 (@jujunghun) and #11 (@bumjoooon) is to use induction on n, and map the hamiltonian cycles (or perfect matchings) to another hamiltonian cycles but in two other reduced graphs. Then by the induction hypothesis to make the conclusion. I didn't read them carefully, but the approach seems ok and the original proof uses the same idea. I tried to read #10 more carefully, since the same idea crossed my mind. I don't think it's ok. The fact that the graph is bipartite was never used. The points is the claim is no longer true without this assumption. Indeed, consider the complete graph K_4 on 4 vertices. It's a 3 regular graph, but not a bipartite one (there are triangles). Note that K_4 has exactly three hamiltonian cycles, so the number is not even. I think, the mistake lies in counting the number of matchings (n_1, n_2, n_3) some other matching (m_1, m_2, m_3) is associated with (in the respected context). It may happen (n_1,n_2,n_3) is the same matching as m_1,m_2,m_3, thus the constructed graph may have loops, and then the so called handshake lemma is no longer valid, so there is no obstacle the number of vertices to be odd, as in the case of K_4. It seems #9 (@jaydoubleuel) also didn't use the bipartite condition. Not sure, but scanning through it, I didn't notice something like that used.
15.11.2024 08:44
Actually this is well known result about hamiltonian cycle, which is proved by J. Bosák in 1967. See《Combinatorial Problems and Exercises》, Chapter 5, Problem 22 for the original solution of Bosák.