Take the star graph so we have $k \le 3$. To show we can always pick $3$, choose a leaf, its neighbour and an arbitrary other vertex, so nothing can be adjacent to all three of these, done.

Every chosen vertex must have at most 2 chosen neighbors, not every vertex.

I guess the answer is 1517 ,is it?

The answer is $1517$. In general, if $f(n)$ is the answer for $n$ vertices, then $f(4k+r)=3k+r$ where $r\in \{0,1,2,3\}$. Another way of putting it is $f(n)=\lceil \frac{3n}{4} \rceil$ Construction: $k$ star graphs of $4$ vertices plus $r$ isolated vertices. There are $4k+r$ vertices total and from each star tree we must miss at least one vertex. It remains to prove that this bound is optimal. Since the more edges the harder, we can assume the graph is a tree. For integers $n,k$, let $R(n,k)$ denote the specific integer in $[0,k)$ such that $k\mid n-R(n,k)$ Claim: [Induction to prove that induction works] Let $T$ be a tree on $n (n\ge 4)$ vertices. There exists a vertex such that upon its removal, the tree is split into subtrees with sizes $s_1,\cdots,s_k$ where $\sum\limits_{j=1}^k R(s_j,4)\ge R(n,4)+3$. We prove this claim by minimality, where $n=4,5,6,7,8$ can done by removing the centroid (the vertex such that upon its removal, splits into subtrees of size at most $\frac n2$, so for $n=4,5,6,7$ the sum is simply $n-1$) of the tree. We just need $\sum\limits_{j=1}^k R(s_j,4)\ge 3$ since $\sum\limits_{j=1}^k R(s_j,4) \equiv \sum s_j \equiv n-1(\bmod\; 4)$ Case 1: there exists an edge $e$ such that there are $4m$ vertices to one side (WLOG left). Let $R$ be the induced subgraph of the vertices on the right side. If $|R|\ge 4$, then by inductive hypothesis we can split $R$ as needed, and the $4m$ vertices won't affect the subtree sizes mod $4$. It follows $|R|<4$. However, if I remove the vertex on the left of $e$ then the left subtrees form a sum $3$ mod 4, then the sum of the remainders is at least $3+R(|R|,4)=3+R(n,4)$, as needed. Case 2: such edge doesn't exist. There exists vertices with degree at least 3, or we can take the entire tree. Remove it. After its removal, by definition of case 2, each subtree upon removal must have a size that is not a multiple of 4. Therefore, $\sum R(s_j,4)\ge \sum 1 \ge 3$ Armed with this claim, we do another induction to prove that $f(4k+r)=3k+r$, or $f(n)=\lceil \frac{3n}{4} \rceil$. We can remove a vertex (i.e. choose to NOT select) such that upon its removal, $\sum\limits_{j=1}^k R(s_j,4)\ge R(n,4)+3$. This means if $s_j=4k_j+r_j$ then I am taking $3\sum k_j + \sum r_j$ while I need $3\sum k_j + \lceil 3(\sum r_j+1)/4 \rceil$. Since $x\ge \lceil 3(\sum r_j+1)/4 \rceil \leftrightarrow x\ge 3$, we are done.

Is R(n,4) the Ramsey number?

The remainder haha. Very sorry

estetasks wrote: Is R(n,4) the Ramsey number? If it's the Ramsey number, then there's no exact answer to this problem by that approach lol

induct to winduct Let the graph be $T$ and call a vertex subset good if the induced subgraph formed by it has maximum degree $2$. Replace $2022$ with $n$. Then the answer is $\lceil \tfrac{3}{4}n \rceil$. Construction: Let $n=4a+b$ with $0 \leq b<4$. Then construct $a$ disjoint star graphs on $4$ vertices each, as well as $b$ isolated vertices. It is evident that we may choose at most $3$ vertices for each star graph, which means we can choose at most $3a+b$ vertices total. This clearly translates to $\lceil \tfrac{3}{4}n \rceil$. Bound: We use induction, with $n \leq 4$ being manually verifiable. Let the graph be $T$ and WLOG let it be connected, since removing edges preserves the validity of a chosen set of vertices. Consider the longest path $v_0\ldots v_m$ in $T$; clearly $m \geq 2$. By deleting $v_1$ we get some number of connected components, two of which are $v_0$ and the connected component containing $v_1\ldots v_m$. Then all the other connected components must be single vertices as well, else we get a longer path. Let $v_0=w_1$ and let $w_2,\ldots,w_k$ be the other single-vertex components generated. If $k=1$, then $\deg v_1=1$, so we may take a maximal good subset of $T \setminus \{v_1\}$ and add a vertex to it. By inductive hypothesis this is enough. If $k=2$. Consider $T':=T \setminus \{v_1,w_1,w_2,v_2\}$. This contains $n-4$ vertices, so by inductive hypothesis it has a good subset with at least $\tfrac{3}{4}(n-4)=\tfrac{3}{4}n-3$ vertices. Then we add $v_1,w_1,w_2$ to this good subset of $T'$, which yields a good subset of $T$ since none of these vertices are adjacent to $T'$, containing at least $\tfrac{3}{4}n$ vertices. If $k \geq 3$, then consider $T':=T \setminus \{v_1,w_1,\ldots,w_k\}$, which contains $n-k-1$ vertices. By adding $w_1,\ldots,w_k$ to a maximal good subset of $T'$, by inductive hypothesis this gives a good subset of $T$ containing at least $$\frac{3}{4}(n-k-1)+k=\frac{3}{4}n+\frac{1}{4}k-\frac{3}{4} \geq \frac{3}{4}n$$vertices, so we're done. Combining these cases finishes the problem. $\blacksquare$ Remark: I think the $k=2$ case is actually harder than the others. This writeup perhaps hides the actual idea behind the $k=2$ case. The idea for $k \geq 3$ actually works for $k=2$ as well, so long as $n \not \equiv 3 \pmod{4}$. When $n \equiv 3 \pmod{4}$ we have to try to induct some other way. If I delete an edge $\overline{vw}$—which is potentially nice, since the number of vertices stays the same and we only have to worry about one possible "collision"—and split $T$ into two subgraphs to apply inductive hypothesis on, this would work as long as one $v,w$ isn't chosen in the maximal good subset of its respective subgraph. The resulting subgraphs are either $1$ and $2$ mod $4$, or $3$ and $4$ mod $4$. Then the tricky, slick idea is that in the latter case we may actually delete the vertex in the $4 \pmod{4}$ subgraph, resulting in something with $3 \pmod{4}$ vertices, and apply inductive hypothesis on the result, the size of the good subset supplied doesn't change when we do this! So if we can delete an edge and split $T$ into subgraphs which are $3$ and $4$ mod $4$ then we just win. It turns out that there's a very easy way to do this: just look at the vertices we already know! Of course, I think it's also possible to arrive at this thought process by considering vertex deletions instead of this somewhat convoluted edge deletion, but I thought about this and got nowhere immediately; perhaps the idea is more concealed, especially since arbitrary vertex deletions would naturally be seen as producing multiple subgraphs, not just two, and therefore the idea to actually use the $n \equiv 3 \pmod{4}$ condition this way is less evident. This is similar to what CBK does in #6.