0
$\begingroup$

Is it possible to transform a graph (which contains K5 or K3,3) by only adding edges or vertices, i.e. by arbitrarily expanding its structure?

$\endgroup$
2
  • 2
    $\begingroup$ If $K_5$ or $K_{3,3}$ are subgraphs of a given graph, they will also be a subgraph of any graph where you've added edges or vertices. $\endgroup$ Commented Jun 29 at 10:05
  • 1
    $\begingroup$ Yes. Draw your graph, and add a vertex everywhere two edges cross. $\endgroup$ Commented Jun 29 at 12:33

1 Answer 1

Reset to default
2
$\begingroup$

A graph cannot be planar if it contains K5 or K3,3. Also, by adding edges and vertices, then K5 and K3,3 are still subgraphs of your original graph, meaning that it is not planar.

$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.