\(\newcommand{\fA}{\mathfrak{A}} \newcommand{\fB}{\mathfrak{B}} \newcommand{\fC}{\mathfrak{C}} \DeclareMathOperator{\Res}{Res} \newcommand{\fD}{\mathfrak{D}} \newcommand{\fE}{\mathfrak{E}} \newcommand{\fF}{\mathfrak{F}} \newcommand{\fG}{\mathfrak{G}} \newcommand{\fH}{\mathfrak{H}} \newcommand{\fI}{\mathfrak{I}} \newcommand{\fJ}{\mathfrak{J}} \newcommand{\fK}{\mathfrak{K}} \newcommand{\fL}{\mathfrak{L}} \newcommand{\fM}{\mathfrak{M}} \newcommand{\fN}{\mathfrak{N}} \newcommand{\fO}{\mathfrak{O}} \newcommand{\fP}{\mathfrak{P}} \newcommand{\fQ}{\mathfrak{Q}} \newcommand{\fR}{\mathfrak{R}} \newcommand{\fS}{\mathfrak{S}} \newcommand{\fT}{\mathfrak{T}} \newcommand{\fU}{\mathfrak{U}} \newcommand{\fV}{\mathfrak{V}} \newcommand{\fW}{\mathfrak{W}} \newcommand{\fX}{\mathfrak{X}} \newcommand{\fY}{\mathfrak{Y}} \newcommand{\fZ}{\mathfrak{Z}} \newcommand{\cA}{\mathcal{A}} \newcommand{\cB}{\mathcal{B}} \newcommand{\cC}{\mathcal{C}} \newcommand{\cD}{\mathcal{D}} \newcommand{\cE}{\mathcal{E}} \newcommand{\cF}{\mathcal{F}} \newcommand{\cG}{\mathcal{G}} \newcommand{\cH}{\mathcal{H}} \newcommand{\cI}{\mathcal{I}} \newcommand{\cJ}{\mathcal{J}} \newcommand{\cK}{\mathcal{K}} \newcommand{\cL}{\mathcal{L}} \newcommand{\cM}{\mathcal{M}} \newcommand{\cN}{\mathcal{N}} \newcommand{\cO}{\mathcal{O}} \newcommand{\cP}{\mathcal{P}} \newcommand{\cQ}{\mathcal{Q}} \newcommand{\cR}{\mathcal{R}} \newcommand{\cS}{\mathcal{S}} \newcommand{\cT}{\mathcal{T}} \newcommand{\cU}{\mathcal{U}} \newcommand{\cV}{\mathcal{V}} \newcommand{\cW}{\mathcal{W}} \newcommand{\cX}{\mathcal{X}}\newcommand{\cx}{\chi} \newcommand{\cY}{\mathcal{Y}} \newcommand{\cZ}{\mathcal{Z}} \DeclareMathOperator{\Aut}{Aut} \newcommand{\bA}{\mathbb{A}} \newcommand{\bB}{\mathbb{B}} \newcommand{\bC}{\mathbb{C}} \newcommand{\bD}{\mathbb{D}} \newcommand{\bE}{\mathbb{E}} \newcommand{\bF}{\mathbb{F}} \newcommand{\bG}{\mathbb{G}} \newcommand{\bH}{\mathbb{H}} \newcommand{\bI}{\mathbb{I}} \newcommand{\bJ}{\mathbb{J}} \newcommand{\bK}{\mathbb{K}} \newcommand{\bL}{\mathbb{L}} \newcommand{\bM}{\mathbb{M}} \newcommand{\bN}{\mathbb{N}} \newcommand{\bO}{\mathbb{O}} \newcommand{\bP}{\mathbb{P}} \newcommand{\bQ}{\mathbb{Q}} \newcommand{\bR}{\mathbb{R}} \newcommand{\bS}{\mathbb{S}} \newcommand{\bT}{\mathbb{T}} \newcommand{\bU}{\mathbb{U}} \newcommand{\bV}{\mathbb{V}} \newcommand{\bW}{\mathbb{W}} \newcommand{\bX}{\mathbb{X}} \newcommand{\bY}{\mathbb{Y}} \newcommand{\bZ}{\mathbb{Z}} \newcommand{\ce}{\mathcal{e}} \newcommand{\fe}{\mathfrak{e}} \newcommand{\p}{\overline{p}} \DeclareMathOperator{\im}{im} \DeclareMathOperator{\rank}{rank} \DeclareMathOperator{\coker}{coker} \DeclareMathOperator{\rad}{rad} \DeclareMathOperator{\spec}{Spec} \DeclareMathOperator{\diam}{diam} \DeclareMathOperator{\maxspec}{maxSpec} \DeclareMathOperator{\Ann}{Ann} \DeclareMathOperator{\Ass}{Ass} \require{AMScd}\)

Thursday, December 13, 2018

A graph with at most one vertex of degree less than 3 has a subdivision of $K_4$

This is about a problem in the Bondy and Murty's book on Graph Theory.
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$.
This is also about a question made by me in math.stackexchange about a case when the graph was $2-$connected but not $3-$connected. My original reasoning was as follows:
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).
But as Misha Lavrov comments there, there is a flaw in the first paragraph of the attempt, which is shown in the following graph.
When contracting an edge incident to the red vertex it becomes the following graph:
which has two vertices of degree two. This can still be solved and the reasoning to do it will be shown next.

Using the Misha's answer and my own remarks, and ignoring the fan-lemma we have the following proof:

Proof. Suppose first that $G$ is not $3-$connected. For such a graph, we'll prove the result by induction on $n=|G|$. For $n=4$ the result is trivial ($G$ must be $K_4$), so we can suppose that $n>1$ and that any graph with less than $n$ vertices and at most one vertex of degree $<3$ contains a subdivision of $K_4$. Now, if, in fact, $G$ is not connected, then its connected components all have at most a vertex of degree $<3$. By induction hypothesis, each of them, besides a possibly trivial one (on which case the rest of them would have minimum degree $\geq 3$) contains a subdivision of $K_4$ so $G$ too. Let's now suppose $G$ is connected, but has a cut-vertex $v$. Let $C$ be a connected component of $G-v$ with no vertex of $G$ with degree $\leq 2$ (this is how we solve the problem mentioned above). Then $G[C\cup v]$ has at most one vertex of degree $2$ ($v$ is the only candidate). By induction hypothesis, $G[C\cup v]$ contains a subdivision of $K_4$; so does $G$, then. 

Now suppose $G$ is $2-$connected but contains a separating set of minimum size $S$ with two vertices. Take $S=\{v,w\}$ in such a way that a component $C$, with no vertices of $G$ with degree $\leq 2$, of minimum size of $G-S$ is as smallest as possible.  

This means that both $v$ and $w$ have two adjacent vertices in $C$. Indeed, if $v$ (resp. $w$) has only one adjacent vertex $v'$ in $C$, then $\{v',w\}$ is another separating set in $G$, with a component being $C'=C-v'$. Also, $C'\neq \varnothing$, in such a case it would happen that $C=\{v'\}$ and $d(v')=2$, a contradiction.

Furthermore, since $v,w$ both have adjacent vertices in any other component of $G-S$, then there exists a $v-w-$path, say, $\gamma$ not meeting $C$.

Take a new graph $G'$ defined as follows: 
$$V(G')=V(C)\cup S,$$
$$E(G')=E(C)\cup E(S,C)\cup \{vw\}.$$

By the choice of $C$, again, $v,w$ have each one at least two edges to $C$, and the edge $vw$, adding $3$ to both degrees, so $d(v),d(w)\geq 3$. Then $\delta(G')\geq 3$ (Since the only changing degrees are the ones of $v,w$). By induction hypothesis, $G'$ contains a subdivision of $K_4$. If $vw\in E(G)$ we're done. If this subdivision uses $vw$ and $vw\notin E(G)$, then, in $G$, replace $vw$ by $\gamma$. It'll still be a subdivision of $K_4$. Therefore, every non-$3-$connected graph with at most one vertex of degree $\leq 2$ has a subdivision of $K_4$.

Now suppose $G$ is $3-$connected. We know, by Tutte's wheel theorem that $K_4$ is a minor of $G$, but we're looking for $K_4$ as a topological minor which is not the same. We'll work as follows: Take a cycle $\zeta$ of $G$ of minimum length, in such a way it's an induced cycle. Since $G$ is $3-$connected, then $G\neq \zeta$ and since $\zeta$ is induced, there is $v\in V(G)-V(\zeta)$. Also $\delta(G)\geq 3$, thus $d(v)\geq 3$. Since $N(v)$ separates $v$ fron $\zeta$, then by Menger's theorem there exist at least three disjoint $v-\zeta-$paths. Three of them, along with $\zeta$, make a subdivision of $K_4$.


Posted by at No comments:
Subscribe to: Comments (Atom)