Rather , isomorphic graphs, planar graph

  • Thread starter iris_m
  • Start date
  • #1
iris_m
8
0
rather urgent :(, isomorphic graphs, planar graph

I need help with the following two problems:

1) Is this graph planar?
9s8nkp.png


2) Are these two graphs isomorphic?
2l97fw5.png


I don't know what to do with these two problems, and I would be really grateful for all your hits and help.

For number 1, I've tried to use the corollaries of Euler's formula, but that gives me nothing, and for number two, I think it has something to to with the fact that one graph has a cycle of order 3, and the other one does not, but I don't know how to prove that isomorphisms preserve k-cyles. :(
Also, the first graph is bipartite, and the other one is not. Does isomorphism preserve this?

Please, help.
 

Answers and Replies

  • #2
iris_m
8
0


Also, the first graph is bipartite, and the other one is not. Does isomorphism preserve this?

Please, help.

Oh, the first one isn't bipartite, I got that wrong..
 
  • #3
36,697
8,687


My graph theory is pretty rusty and not very deep, but the first graph does not appear to be planar because of the edges that cross. Some information that might be helpful can be found at Wikipedia--search for "planar graph".
 
  • #4
iris_m
8
0


My graph theory is pretty rusty and not very deep, but the first graph does not appear to be planar because of the edges that cross. Some information that might be helpful can be found at Wikipedia--search for "planar graph".

If you want to prove that a graph isn't planar, you have to prove that it can not be "drawn" such that its edges don't cross, it is not enough to see that the current drawing isn't planar.
(Sorry about my English, I don't know the right words..)

Also, if anyone wanted to know, the graph indeed isn't planar, because it contains K3, 3, with some added edges.
 

Suggested for: Rather , isomorphic graphs, planar graph

Replies
35
Views
2K
  • Last Post
Replies
7
Views
463
  • Last Post
Replies
2
Views
336
  • Last Post
Replies
6
Views
411
  • Last Post
Replies
3
Views
391
  • Last Post
Replies
10
Views
388
Replies
6
Views
489
Replies
17
Views
467
Replies
6
Views
2K
Top