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

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...

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.

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

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.

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)$.

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.

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.

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.

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.

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?

$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.

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. $

I heard this was one of the highest combination problem's in KMO past years.

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.

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.