Infinite graph theory: What's a tree?

194 Views Asked by At

Consider a finite graph $G$: $G$ is a tree if it satisfies any of the following equivalent conditions:

(1) $G$ is connected and no cycle can be a subgraph of $G$.

(2) $G$ is connected and no cycle can be an induced subgraph of $G$.

If $G$ is infinite (countably), clearly (1) implies (2) but does (2) imply (1)?

1

There are 1 best solutions below

0
On

Hint (same proof as for the finite case)

If there is a cycle (and by definition there are only finite cycles), then pick the smallest cycle and figure out whether it is an induced subgraph.