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

Processing math: 100%

First time here? Check out the FAQ!

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

5426 ●4 ●44 ●121

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: 5 years ago

Seen: 935 times

Last updated: Sep 25 '19