What is the largest possible number of edges in a graph on $2n$ nodes, if there exists exactly one way to split its nodes into $n$ pairs so that the nodes from each pair are connected by an edge? Proposed by Anton Trygub
Problem
Source: Ukrainian Mathematical Olympiad 2023. Day 2, Problem 9.8
Tags: combinatorics, graphs
06.04.2023 14:24
Assume, $(a_i,b_i), i=1,2,\dots,n$ is a certain perfect matching. Denote $A:=\{a_1,a_2,\dots,a_n\}, B:=\{b_1,b_2,\dots,b_n\}.$ Let $G(A,B)$ be the bipartite graph obtained from the original graph $G$ by deleting edges inside $A$ and $B.$ By $G(A)$ and $G(B)$ we denote the induced graphs on $A$ and $B$ correspondingly. Note that $|E(G(A))|+|E(G(B))|\le n(n-1)/2.$ Indeed, assuming the opposite, there will be two edges $a_i a_j$ and $b_i b_j,$ thus instead the matching $(a_ib_i), (a_j,b_j)$ we can consider $(a_i,a_j), (b_i,b_j).$ Further, there is no cycle in $G(A,B),$ otherwise we can find another matching. This means $|G(A,B)|\le 2n-1.$ Therefore, $$|E(G)|\le n(n-1)/2 +2n-1.$$An example of graph with exactly that number of edges can be obtained if we connect all the vertices in $A$ and add $a_ib_i,i=1,2,\dots,n$ and $a_i,b_{i+1}, i=1,2,\dots,n-1.$ This graph contains an unique matching.
07.04.2023 14:03
@above I may be wrong but I think the answer is $n^2$. In the notation of the above solution, we obtain that $|E(G(A))|+|E(G(B))|\le \dfrac{n(n-1)}{2}$. Moreoever, similarly the total number of edges between vertices of $A$ and $B$ that are different from $(a_i,b_i)$ for some $i$ are $\leq \dfrac{n(n-1)}{2},$ since whenever $a_ib_j$ is an edge with $j \neq i$, $a_jb_i$ cannot be an edge since then we could form another matching. Thus, we have in total at most $\dfrac{n(n-1)}{2}+\dfrac{n(n-1)}{2}+n=n^2$ edges at the graph $G$. To obtain this bound, we consider the following graph $G$: let $a_i,b_i$ be its vertices with $i$ running from $1$ to $n$, and connect $a_1$ to all vertices and $a_i$ to all vertices except $b_1,b_2,\ldots,b_{i-1}$ for $i \geq 2$. Moreover, draw no vertices among the $b_i$. We have a total of $n^2$ edges (just note that the degrees of the vertices are $2n-1,2n-2,\ldots,n,n,n-1,\ldots,1$ which sum to $2n^2$, and so by the handshaking lemma we have exactly $n^2$ edges), and a unique matching $(a_i,b_i)$ for $i=1,2,\ldots,n$ (indeed, vertex $b_1$ can only connect to $a_1$. Now, vertex $b_2$ can only connect to $a_2$ since its other neighbor, $a_1$, has already matched with $b_1$. Proceed similarly for all the other $b_i$).
07.04.2023 16:00
@above: Thanks, my bad! The argument in the second half of #2 is incorrect. It's possible a cycle to exists, but there must not be an alternating cycle. That was my intention, but with a slopy implementation! Interestingly, ruling out only recombination among two pairs guarantees the correct estimate!
16.09.2024 21:52
Answer is $n^2$ for $2n$ vertices. Construction for $n^2$: We will induct on $n$. For $n=1,$ two vertices on the graph are connected hence $n^2$ holds. Now suppose that we can consider a graph with $k^2$ edges which contains $2k$ vertices $\{v_i\}_{i\in [1,2k]}$. Add two vertices called $A$ and $B$. Draw $2k+1$ edges $A-v_i$ for $1\leq i\leq 2k$ and $A-B$. Since $deg \ B=1, \ B$ must be pair with $A$ and the rest graph has exactly one perfect matching because of our induction assumption.$\square$ Upper Bound: We will show that a graph with $n^2+1$ edges and $2n$ vertices cannot have exactly one perfect matching partitioning. We induct on $n$ with base case $n=2$. That graph would have more than one perfect matching. Assume that our claim is true for $n-1$. Suppose contrary. Let $u_i-v_i, i\in [1,n]$ be the unique partitioning for perfect matching. If $A,B$ are adjacent, then by our induction assumption $deg \ A+deg \ B\geq 2n+1$ because otherwise total $deg \ G-\{A,B\}\geq (n-1)^2+1$. But this contradicts since $G$ would have at least two perfect matching by induction. Note that $\max\{deg \ u_i, deg \ v_i\}\geq n+1$ since $deg \ A+deg \ B\geq 2n+1$. We can assume that $deg \ u_i\geq deg \ v_i$ thus, $deg \ u_i\geq n+1$. Let $e_i$ be the edge between $u_i$ and $v_i$. $u_i$ is connected to at most $n-1$ distinct $u_j'$s hence $u_i$ has at least $1$ edge between some $v_j$ where $j\neq i$. Set $f(u_i)=v_j$ with latter definition. Draw a red edge between $e_i$ and $e_j$ if $f(u_i)=v_j$. Since the graph $\{e_i\}_{i\in [1,n]}$ has $n$ vertices and at least $n$ edges, there must exist some cycle. Let $e_{k_1},...,e_{k_m}$ be a cycle. Then there is a perfect matching $\{u_{k_i},f(u_{k_i})\}$ which is impossible as desired.$\blacksquare$