Feedback vertex set is a set of vertices whose removal leaves an acyclic graph.
It is known that every vertex transitive graph on $n$ vertices has minimum vertex cover of size $\Omega(n)$. It is also not difficult to show that every connected vertex transitive graph (except for the cycle of length $n$) has minimum feedback vertex set 
of size $\Omega(n/\log^2 n)$. Does $\Omega(n)$ bound hold for the same ?



Does every connected vertex transitive graph on $n$ vertices (except for $C_n$) have minimum feedback vertex set of size $\Omega(n)$?
Let $d \ge 3$ be the degree of the graph. Then the graph has $dn/2$ edges. In order to make it acyclic we must remove at least $(d/2-1)n$ edges, which in turn implies we must remove $(1/2-1/d)n = \Omega(n)$ vertices. Notice that it suffices to assume the graph is $d$ regular, we don't need transitivity. 


