Assume $n\ge 6$ is even. Let $S$ be a set of $n-1$ edges in $K_n$. Suppose there is no perfect matching in $E(K_n)\setminus S$. Then is it true that $S$ must be a star?
I am trying to prove by using Tutte's theorem. But the constraints are not enough somehow: let $U$ be a vertex subset so that the number $t$ of odd componenents in $G[V\setminus U]$ is greater than $t$, then we have $$\binom{t}{2}\le n-1$$ and $$t+1\le n$$ assuming $U\neq\emptyset$.
On
You can prove this with Tutte's Theorem. Let $G$ be $K_n$ with some $n-1$ edges removed. We show that removing $k \geq 1$ vertices of $G$ leaves at most $k$ odd components.
Let $U \subseteq V(G)$ with $|U|=k$, and suppose that $G-U$ has components $C_1, \dots, C_t$ with $t \geq k+1$. If $t=k+1$, then since $|C_1|+\cdots+|C_t| = n-k \equiv k \pmod{2}$, not all of the $C_i$ can be odd, so we are done. Otherwise, we have $t \geq k+2$. The number of non-edges of $G$ is $$ n-1 \geq \binom{n-k}{2} - \sum_{i=1}^t \binom{|C_i|}{2} \geq \binom{n-k}{2} - \binom{n-k-t+1}{2} ,$$ where the second inequality follows from a simple optimization and the constraints that $\sum_{i=1}^t |C_i| = n-k$ and $|C_i| \geq 1$ for all $i$. Simplifying, we have $$ n-1 \geq \frac{1}{2} (t-1)(2n-2k-t) .$$ Since $k+2 \leq t \leq n-k$, we have that $1 \leq k \leq n/2-1$ and $$ n-1 \geq \frac{1}{2} (t-1)(2n-2k-t) \geq \frac{1}{2} \min\{(k+1)(2n-3k-2), (n-k-1)(n-k)\} ,$$ which comes from the fact that this quadratic in $t$ is minimized at the extremes of an interval. Observing that these new bounds are quadratic in $k$, we can further bound $$ n-1 \geq \min\left\{2n-5, \frac{n}{4}(n/2+1) \right\} .$$ For $n\geq 6$, this is a contradiction.
It feels like there should be a shorter proof along these lines, so if anyone sees how to shorten the optimization steps, that would be great.
Yes, the proposition is true. The case $n=6$ can be handled in an exhaustive computer search (which I did). Finding perfect matches can all be done using very simply trial algorithms as the number of possibilities is small.
We use that $n=6$ as the start of mathematical induction, going from $n$ to $n+2$.
So we have a Graph $G$ that is $K_{n+2}$ for even $n \ge 6$ with $n+1$ removed edges. We assume that the removed edges do not form a star and will prove that it has a perfect matching.
We first show that there is an edge in $G$ between 2 nodes, $v_1, v_2$, such that at least $3$ of the removed edges were incident to $v_1$ or $v_2$.
If there is a vertex $v_1$ with $3$ or more incident removed edges, then any edge in $G$ that contains $v_1$ will do. Such an edge exists, since the removed edges do not form a star.
If such a vertex does not exist, it means each vertex has at most $2$ incident removed edges. Since $2(n+1) > n+2$, it means there is a vertex $v_1$ that has exactly $2$ incident removed edges, let's call them $\{v_1,r_1\}$ and $\{v_1,r_2\}$. Removed edges must have endpoints outside of the set $\{v_1, r_1, r_2\},$ because there can be only 3 edges between those 3 vertices. If we take $v_2$ as one such endpoint, the edge $\{v_1,v_2\}$ fullfils our requirements. It is in $G$ (only $\{v_1,r_1\}$ and $\{v_1,r_2\}$ were removed and incident to $v_1$), and among them they have at least $3$ different removed edges incident to them.
We now consider the graph $G'$ which we get from $G$ by removing nodes $v_1, v_2$ and all of their incident edges. $G'$ has $n$ vertices
We can create $G'$ from the complete graph on its $n$ vertices by removing all "mising" edges. Sind $G$ had exactly $n+1$ missing/removed edges from $K_{n+2}$, and at least $3$ of them were incident to $v_1$ or $v_2$, so are not relevant to $G'$, that means $G'$ can be constructed from its complete graph by removing $n+1-3=n-2$ or less edges.
Those $n-2$ or less edges could form a star, but our induction hypothesis is about $n-1$ removed edges. We can remove one or more edges from $G'$ to reach $n-1$ removed edges, and if we remove at least one edge that is not incident with a potential star center, we get a graph $G''$ that can be constructed from a $K_n$ by removing $n-1$ edges that do not form a star. So by the induction hypothesis, we know that $G''$ has a perfect matching.
Since $G''$ is a subgraph of $G'$ and $G'$ is a subgraph of $G$, that matching is also a matching in $G$. Since $G''$ contains all vertives of $G$ except $v_1$ and $v_2$, we can extended that matching, by adding the edge $\{v_1,v_2\}$, to get a perfect matching for our $G$, which concludes the whole proof!