0
$\begingroup$

$M$ is perfect if $M$ covers all vertices of $G$, and $M$ is extendable if $G$ has a perfect matching containing $M$. Moreover, a graph $G$ with at least $2k + 2$ vertices is said to be $k$-extendable if any matching $M$ in $G$ with $|M| = k$ is extendable.

I read Plummer's Theorem from the following paper.

M.D. Plummer. On n-extendable graphs[J].Discrete Mathematics, 1980, 31(2):201–210.

Theorem Let $k$ be a positive integer. If $G$ is an $k$-extendable graph on $n\ge 2k+2$ vertices, $G$ is $(k + 1)$-connected.

I feel like all even cycles $C_n$ for $n\ge 8$ are counter examples. $C_n$ is $\frac{n}{2}$ extendable, but its connectivity is always $2$. The connectivity of $C_n$ is not greater than or equal to $\frac{n}{2}+1(\ge5)$ like the theorem says. What did I get wrong? Thank you in advance.

$\endgroup$
2
  • 1
    $\begingroup$ Is $n\ge2k+2$ in yhour counterexample? $\endgroup$
    – bof
    Commented Sep 13, 2021 at 2:24
  • 1
    $\begingroup$ @bof I see, my counterexample is not correct. (* ̄︶ ̄). $\endgroup$ Commented Sep 13, 2021 at 2:28

0

You must log in to answer this question.

Browse other questions tagged .