# 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. Commented May 6, 2015 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.) Commented May 19, 2015 at 1:53