equivalence between the minor and topological minor of $K_{5}$ or $K_{3,3}$

$\Leftarrow)$ Remark that if a graph G contains $K_{5}$ or $K_{3,3}$ as a topological minor (http://planetmath.org/subdivision) it is easy to see that it also contains respectively $K_{5}$ or $K_{3,3}$ as a minor.

$\Rightarrow)$ Same goes for $K_{3,3}$ as minor. If graph G contains a minor of $K_{3,3}$ as minor it also contains a topological minor (http://planetmath.org/subdivision) of $K_{3,3}$ in G. So it’s suffices to show that if graph G contains a $K_{5}$ as minor, it also contains a $K_{5}$ or $K_{3,3}$ as topological minor (http://planetmath.org/subdivision).

Suppose that $G\succeq K_{5}$, let $K\subseteq G$ be minimal such that $K$ is a minor of $G$. Because $K$ is minimal every branch set of $K$ induces a tree in $K$ and every two branch sets have exactly one edge between them. For every branch tree $V_{x}$ we can add all four edges joining it to the other branches, this way we obtain a tree $T_{x}$. If each of the trees $T_{x}$ is a topological minor (http://planetmath.org/subdivision) of $K_{1,4}$, $K$ will be a topological minor (http://planetmath.org/subdivision) of $K_{5}$. This image should make clear how our $K$ looks like. The big circles are presenting different sets of vertices.

$\xymatrix{&\bigcirc&&\bigcirc\ar@{.}[ll]\inner@par\bigcirc\ar@{.}[ur]\ar@{.}[% urrr]&&&&\bigcirc\ar@{.}[llll]\ar@{.}[ul]\ar@{.}[ulll]\inner@par\bullet\ar@{-}% [u]&\bullet\ar@{-}[uu]&&\bullet\ar@{-}[uu]&\bullet\ar@{-}[u]&T_{x}=MK_{1,4}% \inner@par&&\bigcirc\ar@{-}[urr]\ar@{-}[ur]\ar@{-}[ul]\ar@{-}[ull]&V_{x}}$

If one of the trees is not a $TK_{1,4}$ it has exactly two vertices of degree 3, which means that $K$ is a topological minor (http://planetmath.org/subdivision) of $K_{3,3}$. $K$ now looks like this. The big circles and triangles are presenting different sets of vertices.

$\xymatrix{&\bigtriangleup&\bigcirc\ar@{.}[l]\inner@par\bigtriangleup\ar@{.}[% urr]&&&\bigcirc\ar@{.}[lll]\ar@{.}[ull]\inner@par\bullet\ar@{-}[u]&\bullet\ar@% {-}[uu]&\bullet\ar@{-}[uu]&\bullet\ar@{-}[u]&T_{x}\neq MK_{1,4}\inner@par&% \bigcirc\ar@{-}[ul]\ar@{-}[u]&\bigtriangleup\ar@{-}[u]\ar@{-}[ur]\ar@{-}[l]&V_% {x}}$

Thus if $G\succeq K_{5}$ then $G$ contains a topological minor (http://planetmath.org/subdivision) of $K_{3,3}$ or $K_{5}$. Which proofs this theorem.

Title equivalence between the minor and topological minor of $K_{5}$ or $K_{3,3}$ EquivalenceBetweenTheMinorAndTopologicalMinorOfK5OrK33 2013-03-22 17:47:15 2013-03-22 17:47:15 jwaixs (18148) jwaixs (18148) 11 jwaixs (18148) Proof msc 05C83 msc 05C10