, 2022

We prove first that $N \ge 3n-2$. Consider a graph with $3n-3$ vertices consisting of $n-1$ triangles with vertices $(u_i, v_i, w_i)$ for $i=1, 2, \dots, n-1$ and the path $v_1v_2v_3 \dots v_{n-1}$. It is easy to see that the graph is $n$-good and by deleting any cycle the graph is not connected.

Let $G$ be $n$-good graph having $N = 3n-2$ vertices. First we find a covering tree $T$ of $G$ and color its vertices in two colors. Let $T^{(k)}$ be the tree obtained after adding the first $k$ vertices and $T^{(0)} = \emptyset$. Set $M_k = G \setminus T^{(k)}$. To obtain $T^{(1)}$ we choose arbitrary vertex of $G$, color this vertex in black and add it to $T^{(1)}$. To obtain $T^{(2)}$ we choose a vertex that is a neighbour of the vertex of $T^{(1)}$ (such a vertex exists since $G$ is connected), color this vertex in white and add it and its edge to $T^{(1)}$ in $T^{(2)}$. Assume we have constructed $T^{(k)}$ for some $k \ge 2$. If there are less than $n-1$ white vertices in $T^{(k)}$ in order to obtain $T^{(k+1)}$ we choose a vertex $v$ from $M_k$, that is connected to a white vertex from $T^{(k)}$ (if such a vertex exists) and add this vertex and its edge to a white vertex from $T^{(k)}$ and color $v$ in black. If such a vertex does not exist we choose arbitrary vertex from $M_k$, that is connected to a black vertex, we add it to $T^{(k)}$ and color it in white. If there are $n-1$ white vertices in $T^{(k)}$

then the condition of the problem implies that from any vertex of $M_k$ there is at least one edge to the white vertex of $T^{(k)}$, because there are no neighbouring white vertices in $T^{(k)}$. Therefore we can construct a covering tree $T^{(N)}$ by adding to $T^k$ exactly one vertex from each of the vertices of $M_k$ to the white vertices in $T^{(k)}$ and coloring every vertex from $M_k$ in black. It is easy to see that at the end we get a covering tree $T^{(N)}$ in which no two vertices of the same color are neighbours and there are at most $n-1$ white vertices. Thus there are at least $2n-1$ black vertices in $T^{(N)}$. Consider the subgraph $H$ of $G$ from all black vertices of $T^{(N)}$. Let $H$ contains $m$ connected components $S_1, S_2, \dots, S_m$. Consider covering trees $T_1, T_2, \dots, T_m$ of $S_1, S_2, \dots, S_m$ respectively. Color the vertices in each of $T_1, \dots, T_m$ in blue and red such that no two vertices of the same color are connected. It follows that at least $n$ vertices of $H$ are of the same color. By the condition of the problem there is an edge in these $n$ vertices. Therefore there exists $s \in \{1, \dots, m\}$ such that there is at least an edge in $S_s$ that is not in $T_s$ (because the vertices of the same color are not connected in $T_1, T_2, \dots, T_m$). This implies that there is a cycle in $S_s$. If we delete the edges of this cycle there are no edges from $T^{(N)}$ because no two vertices from $H$ are connected in $T^{(N)}$. Thus, after deleting the edges of this cycle $G$ still contains $T^{(N)}$, i.e. it remains connected.