An independent cut of a graph \(G\) is a vertex set \(S\subset V(G)\) such that \(S\) is an independent set and \(G - S\) is disconnected. Chen and Yu [1] show that every \(n\)-vertex graph with at most \(2n-4\) edges has an independent cut. This bound is tight as the graph consisting of \(n-2\) triangles sharing one edge has no independent cut and \(2n-3\) edges.

Chernyshev, Rauch and Rautenbach [2] introduce forest cuts, i. e., vertex separators that induce a forest. They conjecture that, similar to the result by Chen and Yu, every \(n\)-vertex graph with less than \(3n-6\) edges has a forest cut.¹ As an intermediate goal they state the following problem:

Problem 1. How many edges must an \(n\)-vertex \(3\)-connected graph have such that the neighborhood of every vertex contains a cycle?

Li, Tang and Zhan [3] resolve 1: Every such graph has at least \(\frac{15}{8}n\) edges, while there are such graphs with exactly \(\frac{15}{8}n\) edges. We give a much shorter proof for this.

Theorem 1. Let \(G\) be a \(3\)-connected \(n\)-vertex graph such that for every vertex \(v\in V(G)\) the graph induced by its neighborhood \(G[N(v)]\) contains a cycle. Then \(|E(G)| \geq \frac{15}{8}n\).

Proof. Since \(G\) is \(3\)-connected, every vertex has degree at least \(3\). Consider the partition of \(V(G)\) into the sets \(V_3 \coloneq \{v \in V(G) \mid \deg(v) = 3\}\) and \(V_{\geq 4} \coloneq \{ v\in V(G) \mid \deg(v) \geq 4\}\). Note that the neighborhood of each \(v \in V_3\) induces a triangle since \(G[N(v)]\) contains a cycle.

First, we show that \(V_3\) is an independent set in \(G\). Assume this is not the case. Then, there is a vertex \(v \in V_3\) that has a neighbor \(u \in V_3\). As both \(N(u)\) and \(N(v)\) induce triangles, it follows that \(N(u) \cap N(v)\) is a separator of size \(2\) (see 1) — A contradiction to \(G\) being \(3\)-connected.

Figure 1: If two vertices u,v\in V_3 are adjacent, then N(u) \cap N(v) is a separator of size 2 (highlighted in blue). — Figure 1: If two vertices \(u,v\in V_3\) are adjacent, then \(N(u) \cap N(v)\) is a separator of size \(2\) (highlighted in blue).

Now let us assume that there are two vertices \(u,v \in V_3\) with \(N(u) = N(v)\). Then the graph \(G-u\) is still \(3\)-connected. Furthermore, every neighbor \(u'\) of \(u\) still has a cycle in its neighborhood in \(G-u\), namely a triangle formed by \(v\) and the other two neighbors of \(u\) (see [fig:distinct95neighborhoods]). If \(G\) has at least \(\frac{15}{8}n\) edges we are clearly done. Otherwise, \(G-u\) has less edges than \(G\) (compared to their number of vertices). Thus we may assume that for any two vertices \(u,v \in V_3\) we have \(N(u) \neq N(v)\).

Next, we show that for every vertex \(v \in V_{\geq 4}\) we have that \(|N(v) - V_3| \geq 3\). As \(\deg(v) \geq 4\), this clearly holds if \(v\) has at most one neighbor in \(V_3\). So assume \(u,u' \in N(v) \cap V_3\) with \(u \neq u'\). As \(V_3\) is an independent set, all neighbors of \(u\) and \(u'\) are in \(V_{\geq 4}\). Furthermore, each of \(N(u)\) and \(N(u')\) induces a triangle in \(G\). As \(v \in N(u) \cap N(u')\), it follows that \(N(u) \cup N(u') \subseteq N(v) \cup \{v\}\). Now since \(N(u) \neq N(u')\) (as argued earlier), this gives the desired \(|N(v) - V_3| \geq 3\).

Thus, for every \(v \in V_{\geq 4}\) we have \(\deg(v) \geq 3 + |N(v) \cap V_3|\). As every vertex in \(V_3\) has three neighbors in \(V_{\geq 4}\), we get: \[2|E(G)| \geq \sum_v \deg(v)\geq 3n + 3|V_3| \label{eq:1}\tag{1}\] On the other hand, we can compute: \[2|E(G)| = \sum_v \deg(v) \geq 4n - |V_3| \label{eq:2}\tag{2}\] The sum of 1 and three times 2 gives the desired: \[8|E(G)| \geq 3n+3|V_3| + 3(4n-|V_3|) = 15n \qedhere\] ◻

Theorem 2. There are \(3\)-connected \(n\)-vertex graphs \(G\) with \(\frac{15}{8}n\) edges such that for every vertex \(v\in V(G)\) the graph induced by its neighborhood \(G[N(v)]\) contains a cycle.

Proof. We start with a \(3\)-connected \(3\)-regular graph \(H\), e. g., \(H = C_t \mathop{\mathrm{\Box}}K_2\). We construct \(G\) by replacing each vertex \(v\) of \(H\) by a copy of \(K_4\) such that the three edges incident to \(v\) in \(H\) are incident to different vertices of the \(K_4\) in \(G\), see 2.

Figure 2: The substitution applied to every vertex of H. — Figure 2: The substitution applied to every vertex of \(H\).

It is easy to see that \(G\) is \(3\)-connected since \(H\) is \(3\)-connected. Moreover, as each vertex \(v \in V(G)\) is contained in a copy of \(K_4\), the subgraph \(G[N(v)]\) contains a triangle.

Doing the counting, each vertex of \(H\) corresponds in \(G\) to a copy of \(K_4\) with four vertices and six edges. Thus, we have \(|V(G)| = 4\cdot |V(H)|\) and \(|E(G)| = |E(H)| + 6\cdot |V(H)|\). Since \(H\) is \(3\)-regular, we have \(|E(G)| = \frac{15}{2}\cdot|V(H)| = \frac{15}{8}|V(G)|\). ◻

References↩︎

[1]

G. Chen and X. Yu, Combinatorics, Graph Theory, and Computing“A note on fragile graphs,” Discrete Mathematics, vol. 249, no. 1, pp. 41–43, 2002, doi: https://doi.org/10.1016/S0012-365X(01)00226-6.

[2]

V. Chernyshev, J. Rauch, and D. Rautenbach, “Forest cuts in sparse graphs,” Discrete Mathematics, vol. 348, no. 11, p. 114594, 2025, doi: https://doi.org/10.1016/j.disc.2025.114594.

[3]

C. Li, Y. Tang, and X. Zhan, “The minimum size of a \(3\)-connected locally nonforesty graph.” 2024, [Online]. Available: https://arxiv.org/abs/2410.23702.

According to Chernyshev, Rauch and Rautenbach [2], this has been independently conjectured by Atsushi Kaneko at the 7th C5 Graph Theory Workshop (Kurort Rathen) in 2003.↩︎

Number of Edges in 3-Connected Graphs with Cyclic Neighborhoods

References↩︎

Subjects

Updated on Academus