# Graph minor vs topological graph minor

I still have problem with the notion of a minor versus a topological minor.

1. Prove that $$K_7$$ has $$K_4$$ as a topological minor.

2. Let $$v_1,...,v_6$$ a labeling of $$K_6$$ and let $$G$$ be the graph obtained from $$K_6$$ by removing the edges $$\{v_1v_2,v_1v_3,v_4v_5, v_4v_6\}$$. Prove that $$G$$ contain $$K_5$$ as a minor but not as a topological minor.

1. Be deleting $$3$$ vertices of $$K_7$$ we obtain $$K_4$$ and thus $$K_4$$ is a topological minor of $$K_7$$.

2. By contracting the edge $$v_1v_4$$ we obtain $$K_5$$. Therefore $$K_5$$ is a minor of $$G$$. Since the vertices $$v_2$$, $$v_3$$, $$v_4$$ and $$v_5$$ each have degree $$4$$ and vertices $$v_1$$ and $$v_4$$ each have degree $$3$$, it's impossible for $$K_5$$ to be a topological minor of $$G$$ because if it were, at least five vertices need to have degree $$4$$.

Are my arguments correct?

• Are my arguments corrects ?
– idm
Jun 8, 2015 at 12:36

We say that a graph $$H$$ is a minor of $$G$$ (sometimes denoted $$H \prec G$$) if you can form $$H$$ by deleting vertices, deleting edges, or contracting edges in $$G$$.
We say that $$H$$ is a topological minor of $$G$$ if there exists a subgraph of $$G$$ (the result of deleting edges and vertices in $$G$$) that is isomorphic to a subdivision of $$H$$.