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
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.Sign up to join this community
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.