Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Let $G$ be a connected graph of even order( greater than or equal to 2k) such that every set of $k-1$ independent edges belong to a $1-factor$ of the graph. Then the graph is $k$-connected.
If the fact that $G$ is connected not assumed then the condition that every set of $k$ independent edges belong to a $1-factor$ implies every set of $k-1$ independent edges also belong to a $1-factor$ of $G$ provided the graph has order greater than or equal to 2k+2.
Both statements are false.
Either $P_k$ (if $k$ is even) or $P_{k-1}$ (if $k$ is odd) is a counterexample for the first statement whenever $k\geq4$.
$(k-1)P_2+2K_1$ ($k-1$ disjoint copies of $P_2$ plus 2 isolated vertices) is a counterexample for the second statement.
