Finding a subdivision of $K_4$ in a graph with minimum degree $3$.

Question

In the Bondy and Murty's graph theory book there is the following exercise.

Let $G$ be a nontrivial simple graph with $\delta(G)\geq 3$ or a vertex $v\in V(G)$ such that $\delta(G-v)\geq 3$. Then $G$ has a subdivision of $K_4$.

There, $\delta(G)$ denotes minimum degree.

There are some remarks to do: First, we can reduce the cases to the first one: $\delta(G)\geq 3$. If $d(v)<3$ we can take an edge $e$ such that $v\in e$ and by induction on $|G|$, $G/e$ has a subdivision of $K_4$, so $G$ also has one. We can also suppose $G$ is connected since we can also use induction on its components. We can also suppose $G$ is planar since both $K_5$ and $K_{3,3}$ have subdivisions of $K_4$.

The first thing I tried to do was check (as stated above) that we could suppose $G$ was planar, but my last attempt was checking the connectedness of the graph as follows:

If $G$ is connected, has $\delta(G)\geq 3$ and is not $2-$connected, then take a cut-vertex $v$ and a component $C$ of $G-v$. Then the induced subgraph of $C\cup v$ has at most one vertex of degree $<3$ (the cut-vertex), and by induction we're done. So we can suppose $G$ is $2-$connected. If we can reduce the case to one on which $G$ is $3-$connected then any $3$ vertices are in a common cycle, and then we can apply the Fan Lemma or Menger Theorem appropiately to get the subdivision of $K_4$ (It will be a cycle of length at least $3$ not covering all the vertices and a $3-$fan from one of the remaining vertices to that cycle).

The Fan Lemma. Let $G$ be a $k-$connected graph, let $x$ be a vertex of $G$, and let $Y ⊆ V -\{x\}$ be a set of at least $k$ vertices of $G$. Then there exists a $k-$fan in G from $x$ to $Y$.

So we're left with the case where $G$ is $2-$connected but there is a separating set $S$ with $|S|=2$. But I wasn't able to conclude anything in this case. Is there anything we can do here? If we add the hypothesis of being planar here can it help?

Edit:

As Misha comments, there is a hole in the reasoning when we want to remove a vertex of degree $2$. The graph:

becomes

when contracting an edge incident to the degree-$2$ vertex, and in that case we get, not one, but two new vertices of degree $2$. We can still solve it: When we have a cut vertex $v$, we just take a connected component of $G-v$ with no vertex of $G$ of degree two.

Answer 1

Suppose $G$ has a separating set $S = \{v,w\}$. Let $C$ be the smallest component of $G-S$ that doesn't have any vertices of degree $\le 2$ in $G$, and assume that $S$ is chosen to make $C$ as small as possible.

This, in particular, means that each of $v$ and $w$ has at least two neighbors in $C$. If, say, $w$ has only one neighbor $w'$ in $C$, then $S' = \{v,w'\}$ is another separating set of size $2$, and one of the components of $G-S'$ is $C-\{w'\}$, which is smaller than $C$. (And $C - \{w'\}$ cannot be empty, because then $w'$ would have had degree $\le 2$.)

Also, assuming $G$ is $2$-connected, there is a path connecting $v$ and $w$ outside $C$. Let $x$ be a neighbor of $v$ outside $C$; deleting $v$ should leave a path from $x$ to $C$, which must go through $w$.

Now create a new graph $G'$ in which all vertices outside $C \cup S$ are deleted, and we add a new edge $vw$ if it did not exist already. In $G'$, $v$ and $w$ still have degree at least $3$, and the degrees in $C$ are unchanged.

By induction, $G'$ contains a subdivision of $K_4$. This can be turned into a subdivision of $K_4$ in $G$: if the edge $vw$ is needed and not present in $G$, we can replace it by a path from $v$ to $w$ outside $C$, which we know exists.

---

Alternatively, if you're willing to use some powerful classification results similar to your observation about planar graphs, then you can start from the fact that the graphs with no subdivision of $K_4$ are precisely the series-parallel graphs.

A series-parallel graph must have a vertex of degree $2$. More precisely, a series-parallel graph with source $s$ and sink $t$ either has no other vertices, or else has a vertex of degree $2$ other than $s$ and $t$. To prove this, you can verify that this property is preserved under both series composition and parallel composition:

• A series composition of two $K_2$s results in a path on $3$ vertices, which creates a vertex of degree $2$ other than $s$ and $t$. A parallel composition of two $K_2$s creates a multigraph, so it's not allowed.
• In a series or parallel composition of two graphs, at least one of which has three or more vertices, one of the graphs already had a vertex of degree $2$ other than $s$ and $t$. That vertex still has degree $2$ after the composition.

Therefore a graph with minimum degree $3$ cannot be series-parallel, so it has a subdivision of $K_4$.

We can refine this argument to also rule out graphs in which only one vertex has degree less than $2$. If our series and parallel composition involved at least two graphs with three or more vertices at any point, then each of them had an internal vertex of degree $2$. If not, then $s$ and $t$ can each have degree at most $2$: their degrees increase only with parallel compositions, and we can't parallel-compose a $2$-vertex graph with itself, so for $s$ or $t$ to reach degree $3$, we'd need two larger graphs.