How to find the subgraph homeomorphic to $K_5$ or $K_{3,3}$?

Captcha
65 ●6 ●8 ●16

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?

1 Answer

Sort by » oldest newest most voted

5236 ●3 ●44 ●116

RTFM ?

sage: G = graphs.SchlaefliGraph()
sage: G.is_planar()
False
sage: G.is_planar(kuratowski=True)
(False, Graph on 8 vertices)

Please start posting anonymously - your entry will be published after you log in or create a new account.

1 follower

Asked: 2019-09-25 13:24:59 +0100

Seen: 815 times

Last updated: Sep 25 '19