Is each graph a subdivision of itself? On proving reflexivity of the topological minor relation.

288 Views Asked by At

Diestel writes in his Graph Theory book (Proposition 1.7.1) that

The minor relation and the topological-minor relation are partial orderings on the class of finite graphs, i.e. they are reflexive, antisymmetric and transitive

I proved the three properties for the minor relation but am confused when it comes to the topological-minor relation and proving that it is reflexive. Diestel does not really define if a graph $G$ is counted as a subdividing itself, i.e. having an empty set of subdividing vertices and reading the definition on Proof Wiki sounds like one has to at least subdivide one edge resulting in a non-isomorphic graph $G'$ such that $G'$ is the smallest subdivision of $G$.

However, to prove reflexivity, i.e. $G$ being a topological minor of $G$, $G$ must be in the set of subdividing graphs $TX$. This is due to the fact that the topolocical minor relation is defined as follows: $X$ is a topological minor of $Y$ if there exists a subdivision of X, which is a subgraph of $Y$. Therefore, if $G\notin TX$ because $G'$ is the smallest subdivision of $G$. Then, no graph in $TX$ can be a subgraph of $G$ and hence, $G$ can't be its own topological minor.

Am I misunderstanding how to prove the reflexivity of a topological minor or something in its definition?

PS: This post asked a similar but different question.

1

There are 1 best solutions below

0
On BEST ANSWER

We want the relations to be reflexive, so we define a graph $G$ to be a subdivision of itself.

You could play around with definitions you found in Diestel or on Proof Wiki until this works. For example, Proof Wiki says that $G'$ is a subdivision of $G$ if it is obtained from $G$ by a sequence of edge subdivision operations, so maybe we allow the empty sequence.

But that's missing the point. Definitions are not set in stone; we choose our definitions so that it's easy to say what we want to say with them. It causes multiple problems if we don't allow a graph to be a subdivision of itself. For example, Kuratowski's theorem would have to be changed to "A graph is planar if and only if it does not contain a subdivision of $K_5$ or $K_{3,3}$ and also is not isomorphic to $K_5$ or $K_{3,3}$" which is awkward.

You'll notice that we can still state the theorem even if we make the wrong definitional choice. Similarly, if we said that $G$ is not a subdivision of itself, we could say that the subdivision relation is a strict partial order, instead. The math doesn't change; only how we talk about it does. It's important to choose definitions to make it easiest to talk about the math.