choi eun son

Bump... The fact that 4-regular graph can be partitioned into two 2-regular graph might be useful, but I'm stuck... +) Is it possible to shake hands with some people more than once, i.e. graph can have multiple edge? If it does, problem became too easy. Pick any perfect matching $M$ and add it to every 3-regular graph finishes it.

CBMaster wrote: Bump... The fact that 4-regular graph can be partitioned into two 2-regular graph might be useful, but I'm stuck... +) Is it possible to shake hands with some people more than once, i.e. graph can have multiple edge? If it does, problem became too easy. Pick any perfect matching $M$ and add it to every 3-regular graph finishes it. No, as we wrote the problem we assumed 4 others(4명), instead of 4 times(4번), would clarify the situation. But to be exact, we are referring to simple graphs(which also means no shaking hands with yourself). On a side note, adding a perfect matching is the right approach, but proving its existence is the key to this problem. Imho even the steps after this is not as trivial as it seems.

Easier than I thought... If this is not a fakesolve. The problem asks which of two is larger, number of $3-$regular spanning subgraph of $K_{2024}$ and number of $4-$regular spanning subgraph of $K_{2024}$. We'll prove there are more $4-$regular ones then $3-$regular ones. First, define $A$ be the set of $3-$regular graphs, and $B$ be the set of $4-$regular graphs. And make bipartite graph $G(A, B)$ by connecting $a \in A$ and $b \in B$ iff there exist perfect matching $M$ such that $M$ doesn't have common edge with $a$, and adding $M$ to $a$ makes $b$. If every vertex in $A$ has larger degree then every vertex in $B$, we're done. This is because if we call minimal degree of $A$ be $d_1$ and maximal degree of $B$ be $d_2$, $|E(G)| \geq d_1|A|$, $|E(G)| \leq d_2|B|$ holds. Since $d_2<d_1$, it means $d_1|A| \leq d_2|B|<d_1|B|$ and $|A|<|B|$ holds. Degree of $a \in A$ and $b \in B$ is equal to the number of perfect matchings in complement of $a$(which is $2020-$regular spanning subgraph of $K_{2024}$), $b$ each. So it's suffice to show that $2020-$regular graph has more perfect matchings than $4-$regular graph. We prove it by following two claims. From now, I'll call $k-$regular spanning subgraph of $K_{2024}$ to $k-$regular graph. Claim 1. Every $2020-$regular graph has perfect matching. Proof) Since degree is larger than $\frac{2024}{2}=1012$, It has hamiltonian cycle by Dirac's theorem. Just picking edge of this cycle alternately, we find perfect matching. Claim 2. Every $2020-$regular graph has at least $(1005)!! \cdot 2^{503}$ perfect matching. Proof) Let's number the vertice of graph to $1, ..., 2024$ and WLOG matching in claim 1 was $[1, 2], [3, 4], ..., [2023, 2024]$, and call it $M$. By adding some edges, we'll make $(1005)!!$ types of graphs consist of $503$ $K_4$'s and $6$ $K_2$'s. First, let's call vertex $x$ and edge $[y, z]$ is couple iff $x$ is connected to both $y, z$. Pick $[1, 2]$. Each of vertex $1, 2$ has $2019$ neighbors rather than each other, and there are $1011$ remaining matchings. So there is at least $1008$ couple edges to each vertex, and at least $1005$ common couple to $[1, 2]$. Pick one of them has at least $1005$ ways, and it makes first $K_4$ containing $1, 2$. Next, pick one of remaining $1010$ matching edges. WLOG it was $[5, 6]$. Then each of vertex $5, 6$ has at least $2015$ neighbors rather than each other and $K_4$'s. Since there are $1009$ remaining matchings. So there is at least $1006$ couple edges to each vertex, and at least $1003$ common couple to $[5, 6]$. Pick one of them has at least $1003$ ways, and it makes second $K_4$ containing $5, 6$. In this way, when we reached $k$th step, we can pick $k$th $K_4$ with at least $1007-2k$ ways, and if we reached final step $k=503$, the number of ways that making $K_4$'s will be at least $1005 \cdot 1003 \cdot ... \cdot 3 \cdot 1=(1005)!!$. And each type will be consist of $503$ $K_4$'s and $6$ $K_2$'s, with all of these graphs are all pairwise different(If two different type $A$, $B$ had made first different choice of making $K_4$ in $r$th step, their $r$th $K_4$ must share exactly two vertice, which means two graphs are different). So if we make new matchings to each graph by choosing one of two other matchings in each $K_4$ which is not original $M$, we can make exactly $2^{503}$ ones to each types. It's easy to see they're all different. If they're from same type it's trivial. And if they're from different type, there are two $K_4$ $X$, $Y$ in each type such that $X, Y$ share exactly two vertice $x, y$. $x, y$ must have different matching partner in two chosen matchings. So alltogether, this means there are at least $(1005)!! \cdot 2^{503}$ matchings. Now it's easy to finish it. Every $4-$regular graph has $\frac{2024 \cdot 4}{2}=4048$ edges, so number of perfect matching is less than $2^{4048}$. But $(1005)!! \cdot 2^{503}>2^{4048}$(see here), the problem is solved. Comment 1. While writing this, I've heard and realized that there is much more easier solution. Comment 2. There was a terrible mistake that saying complement of $3-$regular graph is $2021-$regular. What a dumb am I... Anyway, I've fixed it.

Here's easier solution(not mine, the one which I commented above). We will show $2020-$regular graph has at least $\frac{(2020)!!}{4}$ perfect matchings, and $4-$regular graph has at most $2^{2024}$ perfect matchings. 1. For $2020-$regular graph Think abot following algorithm: Pick one vertice $v_1$ and choose one of it's neighbor(call it $v_2$). This makes first edge of matching, and number of choice is $2020$. Then, pick second vertice $v_3(\neq v_1, v_2)$ and choose one of it's neighbor $v_4(\neq v_1, v_2)$. This makes second edge of matching, and number of choice is at least $2018$, since $v_3$'s degree is $2020$ and it can connect to at most two among $v_1, v_2$. In this way if we reached $k$th step, we already made $k-1$ matchings. Pick new vertice(not choosed yet) $v_{2k-1}$, then it has at least $2020-(2k-2)=2022-2k$ neighbors in remaining vertice. So if we choose one of them(call it $v_{2k}$) we can make $k$th edge of matching with number of choice is at least $2022-2k$. This algorithm continues until finishing $1008$th step. After finishing $1008$th step, there will be $8$ vertice remainig. Since each remaining vertices have at least $4$ neighbors in another remaining vertices, there is hamiltonian cycle by Dirac's theorem. So we can make rest $4$ edges of perfect matching by alternately choose edges of hamiltonian cycle, and there are $2$ possibilities. Perfect matchings made by these algorithm are all different, so we can ensure there are at least $2020 \cdot 2018 \cdot ... \cdot 8 \cdot 6 \cdot 2=\frac{(2020)!!}{4}$ perfect matchings. 2. For $4-$ regular graph We use same algorithm above, but this time we can stop this algorithm when we can't find new vertice. More specifically, think about we reached $k$th step and picked $v_{2k-1}$ among non-choosed vertices. If there is neighbor among non-choosed vertice then we can continue, but there is no neighbor, finish algorithm immediately. By this algorithm, every step has at most $4$ ways of choice since graph is $4-$regular. So the total number of matchings found by these algorithm is at most $4^{\frac{2024}{2}}=4^{1012}=2^{2024}$. And it's easy to show that every matching of $4-$regular graph appears in these algorithm. For example, matching $M$ consist of edges $[1, 2], [3, 4], ..., [2023, 2024]$ can appear by this algorithm by following way; If our algorithm first pick vertex $v_1=3$, then $M$ is in subcase when $v_2=4$. Next, if our algorithm pick $v_3=7$ then $M$ is in subcase $v_4=8$, ... Like this, $M$ can be chosen by these algorithm. So this means $4-$regular graph has at most $2^{2024}$ perfect matchings. Since $\frac{(2020)!!}{4}>2^{2024}$, we're done.