Existence of perfect matching with low weight

304 Views Asked by At

Let $k\ge1$, and suppose that $G$ is a $k$-regular and $(k−1)$-edge-connected graph with an even number of vertices, and with edge weights $c:E(G)\to\mathbb{R}$.

Question: Is there always a perfect matching $M$ in $G$ with $c(M)\le \frac1k\cdot c(E(G))$.

Edit: Below are my original thoughts on this problem which turned out to be wrong.

It would obviously suffice to show that there are $k$ pairwise-disjoint perfect matchings of $G$. Let's try to prove this by induction:

If $k=2$ then $G$ is a circle with an even number of vertices and the claim easily follows.

Now assume that $G$ is $(k+1)$-regular and $k$-edge-connected. It easily follows from Tutte's Theorem that $G$ has a pefect matching $M$. Now it would be tempting to apply the inductive hypothesis to $G-M$. However while it is obvios that $G-M$ is $k$-regular it need not be $(k-1)$-edge-connected.

Here is an example of a $3$-regular, $2$-edge-connected graph $G$ with perfect matching (red) $M$ s.t. $G-M$ is not connected (i.e. $1$-edge-connected):

counterexample

But maybe we just picked the wrong matching. We could have also choosen the following one which works:

perfect matching

So it would suffice if every $(k+1)$-regular and $k$-edge-connected graph $G$ with an even number of vertices contained a perfect matching $M$ s.t. $G-M$ is $(k-1)$-edge-connected? (Unfortunetly this turned out to be wrong as shown in the answers)

1

There are 1 best solutions below

1
On BEST ANSWER

The Petersen graph is 3-regular and 2-edge-connected, but not Hamiltonian. Hence, removing any perfect matching results in a disconnected graph.

To be clear, this means that the answer to your question is "no".