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

38 Views Asked by At

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

1

There are 1 best solutions below

0
On

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.