Planar graphs and homomorphism graphs?

Question

I'm working with graphs. I would like to please be verified with this one.

Draw, if possible, a planar representation of each graph:

I got the planar representation of the 2nd graph. This is what I got.

I think the third is not possible. Is that right?

---

Also, do you know how to show that the two graphs are homeomorphic? I understood how to show that graphs are isomorphic, but I'm not really getting homeomorphism. I know that graphs are said to be homeomorphic if both can be obtained from the same graph by subdivisions of edges. But how can I show that they are homeomorphic?

The vertices don't have labels.

Answer 1

As mentionned by Damascuz, for you first question you can use the fact that any planar graph has at most $3n-6$ edges. This limits can be derived from hand-shaking lemma and Euler's formula.

You might also know Kuratowski's theorem : It states that a finite graph is planar if and only if it does not contain a subgraph that is a subdivision of $K_5$ (the complete graph on five vertices) or of $K_{3,3}$ (complete bipartite graph on six vertices, three of which connect to each of the other three).

In your third example, the graph contains a $K_{3,3}$ by grouping the verticex as $\{A,B,F\}$ and $\{C,D,E\}$ for instance.

For your second question. I disagree with Damascuz. Your graph are homeomorphic. The fact that they have the same number of vertices is not sufficient to only check for isomorphism. For the left graph, add a vertex on the diagonal. For the right graph, add a vertex on the handle, the edges that stick out of the square : you will end up with the same graph. Therefore the two graphs are homeomorphic.

Answer 2

There is a criterion for determining whether a graph is planar or not depending on the size $m$ (number of edges) and the order $n$ (number of vertices).

If $G$ is planar, then $m\leq 3n-6$

In your third graph this is clearly not true since $m=13$ and $n=6$.

However, if you'd like a more "geometric" way to prove it, you could try something like this:

Ignore for a moment the edges $AC$ and $DF$. Consider the non-planar representation of both $K_4$'s (complete graphs with 4 vertices) that you have, that is $ABDE$ on one hand, and $BCEF$ on the other.

Try untangling them to see how they are glued by the edge $BE$. Up to this point, you still have a planar graph, and you can see that you can either connect $A$ to $C$ or $D$ to $F$, but not both.

Give it a go, and I'll provide an image/tool for you to see for yourself if you're still not convinced.

In regards to your second question:

Two graphs are homeomorphic if there is a graph isomorphism between some subdivision of each. Since you have the same number of vertices in each case, I don't think you have to consider subdivisions at all and it suffices to prove they are not isomorphic.

Graph isomorphisms are edge-preserving bijections, and clearly this is not the case for those two graphs. Consider $v$ the only vertex with $deg(v)=1$, and suppose there is a bijection $\phi$ from one graph to the other. In graph 1, $v$ is adjacent to some $u$ with $deg(u)=2$. In graph 2 $\phi(v)$ must be adjacent to $\phi(u)$. However, $deg(\phi(u))=3$, which contradicts $\phi$ preserving edge relations.

Hope that helps.