Rather , isomorphic graphs, planar graph

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

This discussion addresses two key problems in graph theory: determining the planarity of a graph and assessing the isomorphism between two graphs. The first graph is confirmed to be non-planar due to the presence of K3,3, which violates the conditions for planarity. Additionally, the discussion highlights that isomorphism does not preserve bipartiteness, as one graph is bipartite while the other is not, and emphasizes the importance of proving non-planarity through edge crossings rather than visual inspection alone.

PREREQUISITES
  • Understanding of Euler's formula in graph theory
  • Knowledge of K3,3 and its implications for graph planarity
  • Familiarity with the concept of graph isomorphism
  • Basic skills in visualizing and drawing graphs
NEXT STEPS
  • Study the properties of planar graphs and the conditions for planarity
  • Learn about graph isomorphism and its implications for graph properties
  • Explore the significance of K3,3 in graph theory and its role in planarity
  • Review techniques for proving non-planarity in graphs
USEFUL FOR

This discussion is beneficial for students and professionals in mathematics, computer science, and graph theory, particularly those dealing with graph analysis, planarity testing, and isomorphism challenges.

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