请输入您要查询的字词:

 

单词 EquivalenceBetweenTheMinorAndTopologicalMinorOfK5OrK33
释义

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


) Remark that if a graph G contains K5 or K3,3 as a topological minor (http://planetmath.org/subdivision) it is easy to see that it also contains respectively K5 or K3,3 as a minor.

) Same goes for K3,3 as minor. If graph G contains a minor of K3,3 as minor it also contains a topological minor (http://planetmath.org/subdivision) of K3,3 in G.So it’s suffices to show that if graph G contains a K5 as minor, it also contains a K5 or K3,3 as topological minor (http://planetmath.org/subdivision).

Suppose that GK5, let KG 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 Vx we can add all four edges joining it to the other branches, this way we obtain a tree Tx.If each of the trees Tx is a topological minor (http://planetmath.org/subdivision) of K1,4, K will be a topological minor (http://planetmath.org/subdivision) of K5. This image should make clear how our K looks like. The big circles are presenting different sets of vertices.

\\xymatrix&&&\\ar@.[ll]\\ar@.[ur]\\ar@.[urrr]&&&&\\ar@.[llll]\\ar@.[ul]\\ar@.[ulll]\\ar@-[u]&\\ar@-[uu]&&\\ar@-[uu]&\\ar@-[u]&Tx=MK1,4&&\\ar@-[urr]\\ar@-[ur]\\ar@-[ul]\\ar@-[ull]&Vx

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

\\xymatrix&&\\ar@.[l]\\ar@.[urr]&&&\\ar@.[lll]\\ar@.[ull]\\ar@-[u]&\\ar@-[uu]&\\ar@-[uu]&\\ar@-[u]&TxMK1,4&\\ar@-[ul]\\ar@-[u]&\\ar@-[u]\\ar@-[ur]\\ar@-[l]&Vx

Thus if GK5 then G contains a topological minor (http://planetmath.org/subdivision) of K3,3 or K5. Which proofs this theorem.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/3 15:26:09