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.
Best Answer
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.