0
$\begingroup$

Let $G=(V,E)$ be a finite, simple, undirected graph. We call $D\subseteq V$ cycle-intersecting if for every simple cycle $C\subseteq V$ we have $C\cap D \neq \emptyset$.

Is there a graph $G$ such that for every cycle-intersecting subset $D$ and for every simple cycle $C$ we have $|C\cap D| > 1$?

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
3
$\begingroup$

No. And this is not about cycles at all.

Take minimal cycle-intersecting subset. If it has at least two vertices from any cycle, remove any vertex from it and get a smaller cycle-intersecting subset.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .