There are $1998$ cities in Dussia, each being connected (in both directions) by flights to three other cities. Any city can be reached by any other city by a sequence of flights. The DSS (Dussia secret service) plans to close off $200$ cities, no two joined by a single flight. Show that this can be done so that any open city can be reached from any other open city by a sequence of flights only passing through open cities.
I don't know how to find such $H$, probably it should be constructed with some algorithm or perhaps take some extrem versions of $H$ (say with minimal or maximal number of neighbour set $N(H)$). Any hint what to do?
While writing this problem, this problem pop out as similar question: Every 3-connected graph has a cycle C such that G-V(C) is connected
Ohh, I can't read, it is 3-connected in that link not 3 regular.
A solution to this problem follows from establishing the following result--which is actually a decent amount stronger, we don't have to settle for merely 200 vertices, we can remove 250 vertices:
Idea of proof: The idea that gives a bound of a bit better than $\frac{n}{10}$ is that you end up with a connected graph $G'$ where the cycles are all vertex-disjoint and so the upper bound on the number of edges is $\frac{4n(G')}{3}$ where $n(G')$ is the number of vertices in $G'$, and this upper-bound is achieved when all the cycles have length 3. [The smaller you can bound the average degree on $G'$, the larger you can guarantee the size of the set of vertices that you can remove.] In fact, we establish that the connected graph $G'$ that we achieve the cycles remain vertex disjoint, and $G'$ is guaranteed to have either many cycles of length 4 or larger, or many vertices not in any cycle.
The proof I gave last would establish a bound of $\frac{n}{10}$ but not $\frac{n}{8}$. The problem was as this: If you contract all degree-2 vertices as in Lemma 3 to an edge then what may result is a multigraph with parallel edges between two vertices and so you cannot assume that the length of the smallest cycle is 3 anymore.
We first make the following observation:
Proof of Claim 1: Removing $v$ makes at least 2 connected components. And so as $v$ has degree-3, there is at least one such component where exactly one edge $e$ incident to $v$ has its endpoint in that component. Then $e$ is a cut edge. $\surd$
We now establish this theorem. Let us suppose that we have already removed an independent set from $G$ so that the resulting graph is still connected. Now let $v$ be a vertex in the remaining graph where $v$ still has degree-3 in the remaining graph and $v$ is not a cut-vertex in the remaining graph. Then if we remove $v$, then the resulting set of vertices that we have removed from $G$ remains independent, and the resulting graph is still connected. Thus we do the following:
(I) If there is an available vertex $v$ that is in a triangle [on the graph that is left], pick a vertex $v'$ that is in a triangle to remove. Otherwise pick another available vertex to remove. STOP when there are no more available vertices to remove. Write as $G'_{int}$ the resulting graph. Then the set of vertices in $G \setminus G'_{int}$ is an independent set of vertices in $G$. Furthermore, $G$ and $G'_{int}$ together have the property:
(A) Let $C$ be a triangle in $G'_{int}$ and let $w'$ be a vertex not in $G \setminus G'_{int}$ such that $w'$ is adjacent in $G$ to a vertex in $C$. Then $w'$ is in a triangle in the original graph $G$.
Indeed, for $w'$ to have been taken out in the first place, by Claim 1 above $w'$ is not incident to any cut edges at the time. So let $v$ be the vertex in $C$ adjacent to $w'$ in $G$. Then $vw'$ was not a cut-edge at the time. As $v$ is in a cycle $C$, neither are the other 2 edges incident to $v$. So $v$ was available. As $v$ is in a triangle, by the rule (I) $w'$ had to have been in a triangle as well.
Then, from $G'_{int}$, do the following if and so long as there is a triangle $C$ in $G'_{int}$ that satisfies the following: There is a vertex $w'$ in $G \setminus G'_{int}$ such that both: (a) The vertex $w'$ is adjacent in $G$ to a vertex $v$ in $C$, and $w'$ is in a triangle in $G$. (b) A triangle $w'x'y'$ that $w'$ is in, in $G$, satisfies the additional property that $x'y'$ is in a cycle in $G'_{int}$.
Then do the following:
Then $G'_{int}$ satisfies the invariant (A) after each of the above iterations as well. Indeed, the set of vertices in a triangle after each iteration is a subset of the set of vertices that were in a triangle before. And every vertex $v$ taken out of $G'_{int}$ was in a triangle in $G'_{int}$ before so $v$ is also in a triangle in $G$.
When there are no more vertices satisfying (a) and (b) above, the resulting graph $G'$ also satisfies (B):
(B) Let $C$ be a triangle in $G'$ and let $w'$ be a vertex not in $G \setminus G'$ such that $w'$ is adjacent in $G$ to a vertex in $C$. Then $w'$ is in a triangle $w'x'y'$ in the original graph $G$, where the additional property is satisfied that both $x',y'$ are not in any cycles in $G'$.
Proof of Claim 2: In $G'$ there are no more available vertices. So all vertices of degree-3 are cut-vertices. Thus by Claim 1, every vertex $v$ of degree-3 is incident to a cut edge. So let $M$ be the set of cut edges. Each such $e \in M$ is not in a cycle, and as every vertex of degree-3 in $G'$ is incident to a cut edge, it follows that $G \setminus M$ has maximum degree-2 and is a collection of vertex-disjoint cycles. As every edge in $M$ is a cut-edge and is in no cycle in $G'$, it follows that the set of cycles in $G' \setminus M$ is the same as the set of cycles in $G' \setminus M$, and these are vertex-disjoint. So the claim follows. $\surd$
Now let $\cal{C}$ be the collection of cycles in $G'$ and for each integer $k$ let us write as $\cal{C}_k$ the set of cycles of length $k$. We now make some observations:
As the cycles are vertex-disjoint, let us collapse each cycle $C \in \cal{C}$ in $G'$ to a vertex $v_C$; the resulting graph $G"_1$ is a tree. Furthermore, every vertex in $G''_1$ is either in $\{v_C; C \in \cal{C}\}$ or in $A$ where $A$ $\doteq \{v \in G'$; $v$ is not in any cycle in $G'\}$. Now let $W'$ be the set of vertices $W'\doteq \{w';$ $w' \in G\setminus G';$ $w'$ is adjacent in $G$ to a vertex in a triangle $C \in \cal{C}_3\}$. By the fact that $G''_1$ is a tree gives the following:
Furthermore, the following is also true:
Proof: As Invariant (A) is maintained, for each cycle $C \in \cal{C}_3$ there are $3-d_{G''_1}(v_C)$ vertices $w'$ in $G \setminus G'$ such that $w'$ is in a triangle in $G$, and $w'$ is adjacent in $G$ to a vertex in $C$. So $w'$ is in $W'$.
Thus, to establish this, it suffices to show that each $w' \in W$ is adjacent in $G$ to exactly one vertex $v$ that is any $C \in \cal{C}_3$. Let $w'$ be a vertex in $W'$, and let $w'x'y'$ be a triangle that $w'$ is in, in the original graph $G$, and let $v$ be the vertices adjacent in $G$ to $w'$ so that $v$ is in a triangle in $G'$. Then $v,x',y'$ are all of $w$'s neighbors in $G$ because $w'$ has degree-3, and furthermore, as (B) is satisfied, $x'$ and $y'$ cannot be in any triangles in $G'$. So the only vertex that $w'$ can be adjacent to that is in a triangle in $G'$, is $v$. Thus indeed, each $w' \in W'$ is adjacent in $G$ to exactly one vertex $v$ that is any $C \in \cal{C}_3$, and so $|W'|$ must be at least $\sum_{C \in \cal{C}_3} [3-d_{G''_1}(v)]$.
So putting Claims 3 and Claims 4 together yields:
We now partition the set $A$ of vertices not in a cycle into 2 sets $A_1$ and $A_{2}$.
The set $A_1$ is defined to be the set of vertices $v \in A$ such that either $v$ has degree-3 in $G''$, or $v$ has degree 2 or 1 but $v$ has no neighbor in $G'' \cap A$ that has degree 2 or 1.
The set $A_{2}$ is the set of vertices $v \in A \setminus A_1$; equivalently, the set of vertices $v \in A$ such that both $v$ has degree-2 or 1, and $v$ is adjacent in $G'$ to another vertex in $A$ that has degree-2 or 1.
Proof of Claim 6: From $G''_1$ contract each path of 2 or more vertices in $A$ of degree 2 or less to a single vertex and let $G''_2$. Then let $A'$ be the set of vertices in $G''_2$ that correspond to vertices in $A$ in $G''_1$. Then $|A_1| + \frac{|A_2|}{2} \ge |A'|$ on the one hand, and on the other hand, $G''_2$ remains a tree, the line of reasoning used to establish Claim 3 above gives: $$|{\cal{C}}_4|+|A'| \ge 1+ \left[\sum_{C \in \cal{C}_3}d_{G''_2}(v_C)\right]-2|\cal{C}_3|.$$
However, $d_{G''_1}(v_C)=d_{G''_2}(v_C)$ for each $C \in \cal{C}$. So this gives
$$|{\cal{C}}_4|+|A'| \ge 1+ \left[\sum_{C \in \cal{C}_3}d_{G''_1}(v_C)\right]-2|\cal{C}_3|.$$
Plugging this together with Claim 4, and then noting $|A_1|+\frac{|A|}{2} \ge |A'|$ yields Claim 6. $\surd$
We also make the following claim:
Proof of Claim 7: We first show the following: Let $w'$ be a vertex in $W'$ and let $w'x'y'$ be a triangle. We claim that the only vertex in $W'$ that $x'$ and $y'$ can be adjacent to is $w'$.
[Indeed, then $x'$ and $y'$ are both in $G'$ and so is the edge $x'y'$. If on the one hand there is another vertex $w'' \in W'$ such that $w''x'y'$ is a triangle then that leaves $D_{G'}(x')=d_{G'}(y')=1$ with the edge $x'y'$ in $G'$ so $x'$ and $y'$ form their own connected component, a contradiction. If on the other hand there is another vertex $w'' \in W'$ such that $w''x'x''$ form a triangle for a vertex $x'' \not = y'$, then $x''$ and $y'$ are 2 distinct vertices in $G'$ and $w'$ and $w''$ are 2 distinct vertices in $G \setminus G'$, all adjacent to $x'$ which gives $d_G(x') \ge 4$.]
We next claim that $w'$ is not adjacent in $G$ to any vertex in $A_1$. Indeed, both $x'$ and $y'$ as above are in $A$ because invariant (B) is satisfied, but both $x'$ and $y'$ have degree no greater than 2 and are adjacent to each other so $x'$ and $y'$ are both not in $A_1$. So Claim 7 follows. $\surd$
Claim 6 and Claim 7 together imply Claim 8:
Claim 8 implies Claim 9:
Then putting this together and doing algebra on the inequality $$\frac{9(n-R)}{7} \ge \frac{3n}{2}-3R$$ yields $R \ge \frac{n}{8}$ and thus the theorem. $\surd$
And this is essentially the best you can do, you cannot guarantee a set larger than $\frac{n}{8}+O(1)$: First let $T_1$ and $T_2$ be 2 complete binary trees of the same size where the roots of $T_1$ and $T_2$ have degree-2 and every other interior vertex of each of $T_1$ and $T_2$ has degree-3. Then
Put an edge between the roots of $T_1$ and $T_2$ and call the resulting graph $T$.
Replace each vertex $v$ of $T$ with a cycle $c_v$, where $c_v$ is a triangle if $v$ is an interior vertex, and $c_v$ is a 4-cycle if $v$ is a leaf.
Then connect the $c_v$s as follows: (a) If $v$ and $w$ are adjacent vertices in $T$ then there is exactly one edge from a vertex in $c_v$ to a vertex in $c_w$; if $v$ and $w$ are non-adjacent distinct vertices in $T$ then there are no edges from $c_v$ to $c_w$. (b) If $v$ is an interior vertex of $T$, then each of the exactly 3 vertices in $c_v$ is adjacent to exactly 1 vertex outside of $c_v$ each. If $v$ is a leaf vertex, then exactly 1 of the exactly 4 vertices in $c_v$ is adjacent to exactly one vertex outside of $c_v$.
Then, for each leaf vertex $v$ of $T$, add an additional vertex $i_v$ and put an edge from $i_v$ to the 3 of the vertices in $c_v$ that have degree exactly 2.
Call the resulting graph $G$. Then if $T$ has $n$ vertices, then $G$ has $5 \times \left(\frac{n}{2}\right)+ 3 \times \left(\frac{n}{2}\right)$ vertices, plus or minus $O(1)$. The largest independent set of vertices that we can remove from $G$ so the resulting graph is connected is $\{i_v; v$ and leaf vertex in $T\}$, and this set has cardinality $\frac{n}{2} = \frac{|V(G)|}{8}+O(1)$. $\surd$