1
$\begingroup$

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.

My Answers:

  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?

$\endgroup$
1
  • $\begingroup$ Are my arguments corrects ? $\endgroup$
    – idm
    Jun 8, 2015 at 12:36

1 Answer 1

0
$\begingroup$

For completeness I'll include the definitions of graph minor and topological graph minor, but yes, your arguments are sound.

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.