What is homeomorphism in graph theory?

Answer 1

The formal definition from Wikipedia "In graph theory, two graphs  and  are homeomorphic if there is a graph isomorphism from some subdivision of  to some subdivision of ."

Let's break down what this means though. Let's first understand what the more stringent graph isomorphism condition is. Two graphs G and G' are said to be isomorphic if there exists a bijection f between their vertex sets, which preserves adjacency. That is, there is an edge between vertices v and w in G iff there is an edge between f(u) and f(v). This means the graphs are identical up to how edges are drawn (to see a good example of this you should check out the Wikipedia page, which has nice drawings).

Subdivisions are pretty straightforward too. You can check out the formal definition on WIkipedia, but the intuition is a bit easier than the formal definition here. All it is is adding vertices on existing edges between other vertices of the graph.

Now we see that the homeomorphism condition for a graph is a bit looser. If you can construct an isomorphism between a subdivision of G and a subdivision of G' then the two graphs are isomorphic. Intuitively, you can view this as meaning that you can draw the graphs in more or less the same shape up to the number of vertices that exist between edges. It's not always that easy to spot when two graphs are homeomorphic because they might be drawn in ways that make them seem very different (especially if one has many vertices and thus many degrees of freedom for how it may be drawn), but luckily there are some useful theorems you can explore to prove the existence of a homeomorphism.