A subset S of the vertex set of a given graph G is acyclic if the subgraph of G induced by S does not consist of any cycle. The maximum order of such an acyclic set in G is denoted by a(G). The author proves three interesting theorems regarding this parameter based on the order and size of the graph G.
The first theorem states that for a connected graph G of order n and size m, a(G)≥(8n-2m-2)/9. In this result they also prove that equality occurs if and only if G consists of K4 and K5 linked by an edge.
The second theorem states that for a triangle-free graph of order n and size m, a(G)≥(20n-5m-5)/19.
According to the third theorem, for a connected planar graph G of order n and size m with girth of at least five, a(G)≥(8n-2m-2)/7, and the equality holds if and only if G is a graph belonging to the collection of polyhedrons of the form D3k+2; k=1, 2, 3, 4, 6.
Each theorem is followed by an equally interesting corollary. The proofs of all three theorems use mathematical induction techniques and progress by establishing several significant claims and facts connecting a(G) and t(G), the expression on the right-hand side of the inequalities in the given theorem. These proofs contain beautiful structural analyses and characterizations of the graphs concerned, and also involve many computational aspects. The content is presented in a systematic and remarkable manner. It is an interesting paper.
