1
$\begingroup$

Definition: Very well covered graph to be a well-covered graph (possibly disconnected, but with no isolated vertices) in which each maximal independent set (and therefore also each minimal vertex cover) contains exactly half of the vertices.

Let $G$ be a very well covered graph.

Prove\disprove: Either $G$ does not have any induced odd cycle or $G$ have $2n$ number of induced odd cycles, where $n > 0$.

$\endgroup$
1
  • $\begingroup$ Why 'or'? Is not 0 also even number? $\endgroup$ Nov 17, 2015 at 17:38

1 Answer 1

3
$\begingroup$

Is the following graph not a counter example?

Consider a graph on 6 vertices $u$, $v$, $w$, $u'$, $v'$, $w'$ with the following structure: $i)$ $u, v, w$ form a triangle, and $ii)$ $u'$ is connected to $u$, $v'$ to $v$ and $w'$ to $w$.

Each maximal independent set appears to contain $3=|V|/2$ vertices, and $G$ contains exactly one induced odd cycle.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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