Every graph contains a linearly sized induced subgraph with all degrees odd (Q2161306)

Let \(G=(V,E)\) be a graph on \(n\) vertices with no isolated vertices. Let \(f_o(G) = \max \{|V_o|:G[V_o]\text{ has all degrees odd}\}\) and let \(f_o(n) = \min \{f_o(G) : G\) is a graph on \(n\) vertices with \(\delta(G) >1\}\). A well-known conjecture is the following. There exists a constant \(c >0\) such that for every \(n \in \mathbb{N}\), we have \(f_o(n) \geq cn\). \textit{Y. Caro} [Discrete Math. 132, No. 1--3, 23--28 (1994; Zbl 0808.05090)] proved that \(f_o(n)= \Omega(\sqrt{n})\). Later, \textit{A. D. Scott} [Comb. Probab. Comput. 1, No. 4, 335--349 (1992; Zbl 0793.05089)] improved this to \(f_o(n) = \Omega(n/ \log n)\). In this self-contained paper, the authors establish the validity of this conjecture with \(c=1/10,000\). They comment that this constant is not optimal.