-2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is there a question? $\endgroup$ – ml0105 Apr 14 '14 at 16:21
  • $\begingroup$ Yes...in first part we have to show it is k-connected and in the second part we have to show that the k-1 set belongs to a 1-factor $\endgroup$ – sayak Apr 14 '14 at 16:25
1
$\begingroup$

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.

$\endgroup$

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.