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):


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)


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

  • 1
    $\begingroup$ As usual, any question beginning with "Does there exist a graph..." has an answer beginning with "The Petersen graph..." $\endgroup$ – Misha Lavrov Oct 17 '17 at 3:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.