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}$
Canonical name	EquivalenceBetweenTheMinorAndTopologicalMinorOfK5OrK33
Date of creation	2013-03-22 17:47:15
Last modified on	2013-03-22 17:47:15
Owner	jwaixs (18148)
Last modified by	jwaixs (18148)
Numerical id	11
Author	jwaixs (18148)
Entry type	Proof
Classification	msc 05C83
Classification	msc 05C10

equivalence between the minor and topological minor of K5 or K3,3

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