How to do it?

To find the largest $m$ such that one of the following is true for any graph $G$ with $n \geq 2$ vertices, you can follow these steps: Step 1: Calculate the minimum degree of each vertex in $G$ to find the maximum number of neighbors that a vertex can have. Let this number be called $m_0$. Step 2: Iterate through each vertex in $G$ and remove any vertices that are adjacent to too many vertices (more than $m_0$) or are part of a cycle with too many vertices. Continue this process until either there are no more vertices to remove or all vertices are connected to fewer than $m_0$ other vertices. Step 3: Count the number of remaining vertices to find the largest $m$ such that one of the following is true: 1. There exists a cycle with at least $k \geq m$ vertices. 2. There exists an independent set with $m$ vertices. Note: This process assumes that you have access to a computer program or a graph-drawing tool that can efficiently identify cycles and independent sets in a graph. If you are working with a large graph, it might be difficult to find a solution manually. Therefore, it is recommended to use a graph-drawing tool or programming language to perform this task efficiently.

envision2017 wrote: To find the largest $m$ such that one of the following is true for any graph $G$ with $n \geq 2$ vertices, you can follow these steps: Step 1: Calculate the minimum degree of each vertex in $G$ to find the maximum number of neighbors that a vertex can have. Let this number be called $m_0$. Step 2: Iterate through each vertex in $G$ and remove any vertices that are adjacent to too many vertices (more than $m_0$) or are part of a cycle with too many vertices. Continue this process until either there are no more vertices to remove or all vertices are connected to fewer than $m_0$ other vertices. Step 3: Count the number of remaining vertices to find the largest $m$ such that one of the following is true: 1. There exists a cycle with at least $k \geq m$ vertices. 2. There exists an independent set with $m$ vertices. Note: This process assumes that you have access to a computer program or a graph-drawing tool that can efficiently identify cycles and independent sets in a graph. If you are working with a large graph, it might be difficult to find a solution manually. Therefore, it is recommended to use a graph-drawing tool or programming language to perform this task efficiently. is this by ChatGPT?

Answer: $\lceil \sqrt{n}\rceil$. Upper Bound: Let $n=k^2+m$ where $m\leq 2k$. Take $k-1$ cliques where all of them have $k+1$ vertices and two cliques whose total number of vertices is $m+1\leq 2k+1<2(k+1)$. There exists an edge among any $k+2$ vertices and there is no cycle with length $k+2$. Thus answer is at most $k+1$ for $k^2+m$. Lower Bound: Assume that there is no cycle with length $\geq k+1$ and no independent set with $k+1$ vertices in graph $G$ with $k^2+m$ vertices. Draw red edges between all non-neighbours. By Turan's theorem, we have \[\binom{k^2+m}{2}-\frac{\sum{deg}}{2}=\frac{\sum{(blue \ deg)}}{2}\geq (1-\frac{1}{k+1}).\frac{(k^2+m)^2}{2}\iff \sum{deg}\leq (k^2+m)(k^2+m-1)-(k^2+m)^2.\frac{k}{k+1}\]\[\sum{deg}\leq (k^2+m)(\frac{k^2+m}{k+1}-1)\]Also, by Caro-Wei Theorem, we have \[k+1>\sum{\frac{1}{\deg{v}+1}}\geq \frac{(k^2+m)^2}{\sum{deg}+k^2+m}\iff \sum{deg}>\frac{(k^2+m)^2-(k^2+m)(k+1)}{k+1}\]Hence, \[(k^2+m)(\frac{k^2+m}{k+1}-1)\geq \sum{deg}>\frac{(k^2+m)^2-(k^2+m)(k+1)}{k+1}\]\[k^2+m-k-1>k^2+m-k-1\]Which is impossible as desired.$\blacksquare$