ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 25 Sep 2019 14:14:41 +0200How to find the subgraph homeomorphic to $K_5$ or $K_{3,3}$?https://ask.sagemath.org/question/48055/how-to-find-the-subgraph-homeomorphic-to-k_5-or-k_33/ Given a graph $ G$ it is easy to check whether the Graph is planar or not using the command "$G$.is_planar()"
However I am stuck on the following :
Given a non-planar graph $G$ is it possible to find a subgraph of $G$ which is homeomorphic to $K_5$ or $K_{3,3}$?
As per Kuratowski Theorem any Graph $G$ is planar if and only if $G$ has a subgraph homeomorphic to $K_5$ or $K_{3,3}$.
Is it possible to find the required subgraph using sagemath?
Wed, 25 Sep 2019 13:24:59 +0200https://ask.sagemath.org/question/48055/how-to-find-the-subgraph-homeomorphic-to-k_5-or-k_33/Answer by FrédéricC for <p>Given a graph $ G$ it is easy to check whether the Graph is planar or not using the command "$G$.is_planar()"</p>
<p>However I am stuck on the following :</p>
<p>Given a non-planar graph $G$ is it possible to find a subgraph of $G$ which is homeomorphic to $K_5$ or $K_{3,3}$?</p>
<p>As per Kuratowski Theorem any Graph $G$ is planar if and only if $G$ has a subgraph homeomorphic to $K_5$ or $K_{3,3}$.</p>
<p>Is it possible to find the required subgraph using sagemath?</p>
https://ask.sagemath.org/question/48055/how-to-find-the-subgraph-homeomorphic-to-k_5-or-k_33/?answer=48057#post-id-48057RTFM ?
sage: G = graphs.SchlaefliGraph()
sage: G.is_planar()
False
sage: G.is_planar(kuratowski=True)
(False, Graph on 8 vertices)
Wed, 25 Sep 2019 14:14:41 +0200https://ask.sagemath.org/question/48055/how-to-find-the-subgraph-homeomorphic-to-k_5-or-k_33/?answer=48057#post-id-48057