Subscribe to the weekly news from TrueShelf


Trees and non-planarity

Let \(V\) be a set of vertices, and let \(T_1=(V,E_1)\), \(T_2=(V,E_2)\), and \(T_3=(V,E_3)\) be three trees on the vertices of \(V\) with disjoint sets of edges: \(E_1\cap E_2 = E_2\cap E_3 = E_3\cap E_1 = \emptyset\). Let \(G=(V,E_1\cup E_2 \cup E_3)\) be the union of the three trees.

Prove that \(G\) is not planar.

Related Content