0
$\begingroup$

1-a graph GG with vertex number >=3 is a cycle-free if and only if every induced subgraph of GG is a tree?

2- an eulrian graph with numbre of vertex >3 is a cyclefree?

for me both statement are false what do you think guys? thank you

$\endgroup$

1 Answer 1

1
$\begingroup$

1) $\Rightarrow$ is right, because if the graph $GG$ contains a cycle then a subgraph induced on its vertices cannot be a tree. But $\Leftarrow$ is wrong. For instance, a union $GG$ of two disjoint trees is cycle-free, but $GG$ itself is not a tree, because it is disconnected.

2) A Eulerian graph contains a Eulerian cycle, so it cannot be cycle-free.

$\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.