Ask Your Question

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

asked 2019-09-25 06:24:59 -0600

Captcha gravatar image

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?

edit retag flag offensive close merge delete

1 answer

Sort by » oldest newest most voted

answered 2019-09-25 07:14:41 -0600

FrédéricC gravatar image


sage: G = graphs.SchlaefliGraph()
sage: G.is_planar()
sage: G.is_planar(kuratowski=True)
(False, Graph on 8 vertices)
edit flag offensive delete link more

Your Answer

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

Add Answer

Question Tools

1 follower


Asked: 2019-09-25 06:24:59 -0600

Seen: 207 times

Last updated: Sep 25 '19