Existence of 1-factor in a connected graph and its connctivity

321 Views Asked by At

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.

1

There are 1 best solutions below

0
On

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.