Rather , isomorphic graphs, planar graph

  • Thread starter iris_m
  • Start date
  • #1
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
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
34,528
6,221


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

Related Threads on Rather , isomorphic graphs, planar graph

  • Last Post
Replies
1
Views
947
  • Last Post
Replies
2
Views
996
  • Last Post
Replies
0
Views
3K
Replies
6
Views
874
Replies
0
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
12
Views
3K
Top