# Does every connected vertex transitive graph on $n$ vertices (except for $C_n$) have minimum feedback vertex set of size $\Omega(n)$?

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 ?

• I guess you mean "minimum feedback vertex set", etc. – Brendan McKay May 6 '15 at 2:32

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.
• Note also that this is $\Omega(n)$ only if $d>2$; but if $d=2$, then (assuming connectedness) we are in the cycle case that was excluded. (Indeed, it seems that otherwise, not only do you not need transitivity, you don't even need connectedness.) – Harry Altman May 19 '15 at 1:53