On the maximum induced forests of a connected cubic graph without triangles (Q757394): Difference between revisions

Let t(G) denote the cardinality of a maximum induced forest of a graph G with n vertices. This paper proves that t(G)\(\geq \frac{2n}{3}\) for any cubic graph G without triangles, except for two cubic graphs with \(n=8\) and \(t(G)=5\). This lower bound is best possible and implies that Speckenmeyer's conjecture is true with two exceptions.