Rather , isomorphic graphs, planar graph

  • Thread starter Thread starter iris_m
  • Start date Start date
  • Tags Tags
    Graph Graphs
Click For Summary

Homework Help Overview

The discussion revolves around two problems related to graph theory: determining the planarity of a graph and assessing whether two graphs are isomorphic. The original poster expresses uncertainty about how to approach these problems, particularly in relation to Euler's formula and the properties of cycles in isomorphic graphs.

Discussion Character

  • Exploratory, Assumption checking, Conceptual clarification

Approaches and Questions Raised

  • The original poster attempts to apply Euler's formula to assess planarity but finds it unhelpful. They also consider the implications of cycle orders on isomorphism and question whether isomorphism preserves properties like bipartiteness.

Discussion Status

Some participants have contributed observations regarding the planarity of the first graph, noting edge crossings as a potential indicator. There is mention of needing to prove non-planarity through specific criteria rather than visual inspection alone. The discussion includes varying levels of familiarity with graph theory concepts, and while some guidance has been offered, no consensus has been reached on the problems.

Contextual Notes

Participants are navigating through potential misconceptions, such as the bipartiteness of the graphs in question. The original poster's initial confusion about the properties of the graphs may influence the discussion.

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.
 

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
3K
  • · Replies 4 ·
Replies
4
Views
3K