# 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\u2ab0{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.

$\text{xymatrix}\mathrm{\&}\u25cb\mathrm{\&}\mathrm{\&}\u25cb\text{ar}\mathrm{@}.[ll]\u25cb\text{ar}\mathrm{@}.[ur]\text{ar}\mathrm{@}.[urrr]\mathrm{\&}\mathrm{\&}\mathrm{\&}\mathrm{\&}\u25cb\text{ar}\mathrm{@}.[llll]\text{ar}\mathrm{@}.[ul]\text{ar}\mathrm{@}.[ulll]\bullet \text{ar}\mathrm{@}-[u]\mathrm{\&}\bullet \text{ar}\mathrm{@}-[uu]\mathrm{\&}\mathrm{\&}\bullet \text{ar}\mathrm{@}-[uu]\mathrm{\&}\bullet \text{ar}\mathrm{@}-[u]\mathrm{\&}{T}_{x}=M{K}_{1,4}\mathrm{\&}\mathrm{\&}\u25cb\text{ar}\mathrm{@}-[urr]\text{ar}\mathrm{@}-[ur]\text{ar}\mathrm{@}-[ul]\text{ar}\mathrm{@}-[ull]\mathrm{\&}{V}_{x}$

If one of the trees is not a $T{K}_{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.

$\text{xymatrix}\mathrm{\&}\u25b3\mathrm{\&}\u25cb\text{ar}\mathrm{@}.[l]\u25b3\text{ar}\mathrm{@}.[urr]\mathrm{\&}\mathrm{\&}\mathrm{\&}\u25cb\text{ar}\mathrm{@}.[lll]\text{ar}\mathrm{@}.[ull]\bullet \text{ar}\mathrm{@}-[u]\mathrm{\&}\bullet \text{ar}\mathrm{@}-[uu]\mathrm{\&}\bullet \text{ar}\mathrm{@}-[uu]\mathrm{\&}\bullet \text{ar}\mathrm{@}-[u]\mathrm{\&}{T}_{x}\ne M{K}_{1,4}\mathrm{\&}\u25cb\text{ar}\mathrm{@}-[ul]\text{ar}\mathrm{@}-[u]\mathrm{\&}\u25b3\text{ar}\mathrm{@}-[u]\text{ar}\mathrm{@}-[ur]\text{ar}\mathrm{@}-[l]\mathrm{\&}{V}_{x}$

Thus if $G\u2ab0{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 |