Ask Your Question

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

asked 2019-09-25 13:24:59 +0200

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 14:14:41 +0200

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 13:24:59 +0200

Seen: 645 times

Last updated: Sep 25 '19