Rather , isomorphic graphs, planar graph

  • Thread starter Thread starter iris_m
  • Start date Start date
  • Tags Tags
    Graph Graphs
Click For Summary
The discussion focuses on two main problems regarding graph theory: determining if a graph is planar and checking if two graphs are isomorphic. The first graph is concluded to be non-planar due to the presence of K3,3, which indicates that it cannot be drawn without edge crossings. For the second problem, it is noted that one graph contains a cycle of order 3 while the other does not, suggesting they are not isomorphic. Additionally, the distinction between bipartite and non-bipartite graphs is highlighted, with clarification that isomorphism does not preserve bipartiteness. Overall, the user seeks assistance in understanding these concepts and proving their assertions.
iris_m
Messages
8
Reaction score
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.
 
Physics news on Phys.org


iris_m said:
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..
 


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


Mark44 said:
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.
 
Question: A clock's minute hand has length 4 and its hour hand has length 3. What is the distance between the tips at the moment when it is increasing most rapidly?(Putnam Exam Question) Answer: Making assumption that both the hands moves at constant angular velocities, the answer is ## \sqrt{7} .## But don't you think this assumption is somewhat doubtful and wrong?

Similar threads

  • · Replies 6 ·
Replies
6
Views
3K
  • · Replies 3 ·
Replies
3
Views
2K
Replies
9
Views
2K
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
Replies
3
Views
3K
  • · Replies 2 ·
Replies
2
Views
5K
Replies
2
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 4 ·
Replies
4
Views
3K