, 2023

Let us first remove vertices of smallest degree from the graph one by one, until in the remaining graph $G' = (V', E')$ every vertex has degree greater than $n^{1/2}$. Note that the above operation removes at most $n \times n^{1/2}$ edges, hence $|E'| \ge n^{3/2}$, and thus $m = |V'| \ge \sqrt{2|E'|} \ge n^{3/4}$.

Take arbitrarily a vertex $v$ in $V'$, and let $V_1$ and $V_2$ be respectively the sets of vertices in $V$ at distance 1 and 2 from $v$. Color all edges from $v$ to $V_1$ blue. Moreover, for each vertex $y$ in $V_2$, choose a vertex $x$ in $V_1$ that is connected to $y$, and color $xy$ blue as well.

We claim that we can always find at least $k$ distinct 3-cycles or 4-cycles passing through $v$. First, since $|V_1| = \deg(v) > n^{1/2} \ge m^{1/2}$, this means that the number of edges from $V_1$ to $V_1 \cap V_2$ is at least $m^{1/2}$. But at the same time, note that the number of blue edges is $|V_2| \le |V| - |V_1| < m - m^{1/2}$, hence this shows that among the edges from $V_1$ to $V_1 \cap V_2$, at least $m^{1/2} \ge k$ of them are not blue, and each such edge, together with at most three blue edges, forms a 3-cycle passing through $v$ (if it goes from $V_1$ to $V_1$) or a 4-cycle (if it goes from $V_1$ to $V_2$).

Now, let $C$ be the union of these 3-cycles and 4-cycles. Note that $C$ has at most $3k+1$ vertices (noting that they all share the vertex $v$), and the total number of edges exceeds the total number of vertices by $k-1$ (based on the structure of the cycles). This shows that, as long as the connected component containing the initially chosen $v$ has at least $3k+1$ vertices, we can start from $C$ and gradually add new vertices from the connected region, until the total number of vertices reaches $3k+1$, at which point the total number of edges is at least $(3k+1) + (k-1) = 4k$. Q.E.D.