Show that if G is simple and has at most one vertex of degree less than three, then G contains a subdivision of K4 •

Question

We know if G is simple and all degrees are at 3 then has subdivision of K4 but I don't know how to prove if G has at most one vertex at most two then G has subdivision of K4.

Answer 1

We first claim that we can reduce this to instances where every vertex has degree at least 3. Indeed, suppose that $G$ has one vertex of degree 2. Then let $G'$ be the graph consisting of two vertex-disjoint copies $G_1$ and $G_2$ of $G$ with an edge added between the degree-2 vertex in $G_1$ and the degree-2 vertex in $G_2$. Then $G'$ has minimum degree 3, and note the following: If there is a subdivision of $K_4$ in $G'$ then there is a subdivision of $K_4$ in either $G_1$ or $G_2$ [i.e., a subdivision of $K_4$ where some but not all of the vertices of the subdivision are in $G_1$ and the remaining vertices are in $G_2$, is not possible]. Now suppose that $G$ has one vertex of degree 1. Then let $\tilde{G}$ be $G$ minus the degree-1 vertex, then every vertex in $\tilde{G}$ has degree at least 2 and all but at most one has degree 3. Finish as above.

**So from the above we may and will now assume that $G$ has minimum degree 3.

Let $C$ be a cycle in $G$ [make sure you see why $G$ has a cycle]. Furthermore, let us assume that $C$ is chordless. [Indeed, let $C$ be a cycle in $G$ that is not chordless. Then we may assume that $C$ has at least 4 vertices. Now as $G$ is simple it is always possible to find a shorter cycle $C'$ that has at least 3 vertices. Indeed write $C = v_0v_1\ldots v_rv_0$ for some $r$ and let $v_iv_j$ be a chord in $G$ with $i+1<j$ and $i \not = j$ mod $r+1$. Then let $C'= v_iv_j\ldots v_rv_1 \ldots v_{i-1}v_i$.

So now let $C$ be a chordless cycle in $G$ that satisfies the following: Let $\ell$ be the size of the largest connected component of $G \setminus V(C)$ [size defined to be the number of vertices]. Then for every other chordless cycle $C'$ the size of the largest connected component of $G \setminus V(C')$ is no larger than $\ell$.

So now we partition into 3 cases.

Case 1: $G \setminus V(C)$ is one component $L$. Then as every vertex in $G$ has degree at least 3 and $C$ is chordless, the following holds: At least 3 vertices $v_1,v_2,v_3$ in $C$ are adjacent to a vertex in $L$ [make sure you see why]. Let $u_1,u_2,u_3$ be the (not necessarily distinct) vertices in $L$ such that $u_iv_i$ is an edge. If $u_1,u_2,u_3$ are 3 distinct vertices then there is a tree $T$ in $L$ with at most one degree-3 vertex $u_4$ (degree-3 in $T$ that is) that has as leaves $u_1$, $u_2$, and $u_3$. Then $v_1,v_2,v_3,v_4=u_4$ form a subdivision of $K_4$ [make sure you see why; first note that $v_1,v_2,v_3$ form a subdivision of $K_3$ in $C$]. If $T$ is a path then assume WLOG that $u_2$ is between $u_1$ and $u_3$ in $T$; then $v_1,v_2,v_3,v_4=u_2$ forma subdivision of $K_4$. If $u_1,u_2,u_3$ is only two distinct vertices then assume WLOG that $u_1$ is adjcaent in $G$ to both $v_1$ and $v_2$. Then as there is a path in $L$ from $u_1$ to $u_3$ it follows that $v_1,v_2,v_3,v_4=u_1$ form a subdivision of $K_4$. [What about the case where $u_1,u_2,u_3$ are the same vertex]

Case 2: $G \setminus V(C)$ has more than one component, but the following still holds: There is a component $L$ of $G \setminus V(C)$ such that least 3 vertices $v_1,v_2,v_3$ in $C$ are adjacent to a vertex in $L$. Finish as in Case 1.

Case 3: For every component $L$ of $G \setminus V(C)$, there are at most 2 vertices $v_1, v_2$ n $C$ that are adjacent in $G$ to a vertex in $L$. As every vertex in $G$ has degree 3 and $C$ has no chords, this implies that there are at least 2 components of $G \setminus V(C)$, so let $L$ be a component with the smallest number of vertices and let $L'$ be a component distinct from $L$ with the largest number of vertices--i.e., $L'$ has $\ell$ vertices with $\ell$ as defined above. Then $v_1$ and $v_2$ can have at most one common neighbour in $L$ ; otherwise if $u_1$ and $u_2$ are both in $L$ and adjacent to $v_1$ and $v_2$ then $u_1,v_1,u_2,v_2$ form a subdivision of $K_4$ [make sure you see why; note that there is a apth in $L$ between $u_1$ and $u_2$]. So as every vertex in $G$ has degree 3, it follows that every vertex in $L$ save one has degree at least 2 in the induced subgraph of $G$ on $L$ [because all but at most one vertex in $L$ is adjacent to at most one of $v_1$, $v_2$] so there is a cycle $C_1$ in $L$ [indeed, every cycle-less graph w at least one edge has at least 2 vertices of degree 1]. And by the same reasoning above that we used to assume that $C$ is chordless, we may assume that $C_1$ is also chordless. But then $L'$ and $C$ are in the same component $L''$ of $G \setminus V(C_1)$, so the number of vertices in $L''$ is strictly larger than the number $\ell$ of vertices in $L'$, which is a contradiction against how $C$ was specified.