Problem 2190

Answer: 1517.
Consider a graph on $n$ vertices having no cycles. By induction over $n$, we will show that the maximum possible value of $k$ is $\lfloor 3n/4 \rfloor$.

It can be readily shown that the claim holds for $n \le 4$. Let $G$ be an acyclic graph on $n \ge 5$ vertices. Assume that the claim holds for all values not exceeding $n-1$. If $G$ is disconnected, then the result follows by applying the induction hypothesis to each connected component. Hence we can assume that $G$ is a tree. There is a unique path between any pair of vertices in a tree. For any $x, y \in V(G)$, let $dist(x, y)$ be the length of the path between $x$ and $y$.

Pick a vertex $r$ in $G$, and partition the vertices of $G$ with respect to their distances to $r$, i.e. let $A_t = \{v \in V(G) : dist(v, r) = t\}$. It can be easily observed that any $v \in A_t$ has exactly one neighbour in $A_{t-1}$. Let $m = \max_{t \ge 0}\{t : A_t \ne \emptyset\}$, and pick $v \in A_m$. If $m = 1$, then we can choose all the vertices except $r$, which completes the proof since $n-1 \ge \lfloor 3n/4 \rfloor$. Assume $m \ge 2$, denote the unique neighbour of $v$ in $A_{m-1}$ by $w$, and denote the unique neighbour of $w$ in $A_{m-2}$ by $x$.

If $\deg(w) = 2$, then we can choose $\lceil 3(n-3)/4 \rceil$ vertices from $G - \{v, w, x\}$ by the induction hypothesis. By adding $v$ and $w$ into the selected vertices, the result will follow since $\lceil 3(n-3)/4 \rceil + 2 \ge \lceil 3n/4 \rceil$.

If $\deg(w) = 3$, let $y$ be the third neighbour of $w$ (other than $x$ and $v$). Then we can choose $\lceil 3(n-4)/4 \rceil$ vertices from $G - \{v, w, x, y\}$ by the induction hypothesis. By adding $\{w, v, y\}$ into the selected vertices, the result will follow since $\lceil 3(n-4)/4 \rceil + 3 = \lceil 3n/4 \rceil$.

If $\deg(w) \ge 4$, let $N$ be the set of neighbours of $w$ in $A_m$, thus $N$ includes $s \ge 3$ vertices. By the induction hypothesis, we can choose $\lceil 3(n-s-1)/4 \rceil$ vertices from $G - (N \cup \{w\})$. Then, by adding $N$ into the selected vertices, the result will follow since $\lceil 3(n-s-1)/4 \rceil + s \ge \lceil 3n/4 \rceil$.