Rather , isomorphic graphs, planar graph

In summary, the conversation discusses two problems: determining if a graph is planar and if two graphs are isomorphic. The first graph appears to not be planar due to crossing edges, and the second problem involves proving that isomorphisms preserve k-cycles and bipartite structures. Additional information and resources are suggested for further understanding of these concepts.
  • #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.
 
Physics news on Phys.org
  • #2


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..
 
  • #3


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


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.
 

FAQ: Rather , isomorphic graphs, planar graph

What is a rather graph?

A rather graph is a type of graph where each node has a unique label, and edges are directed and labeled. This means that each edge specifies a specific direction and is associated with a specific label.

What is an isomorphic graph?

An isomorphic graph is a type of graph where two graphs have the same structure, meaning they have the same number of nodes and edges, and the same connections between them. The only difference between isomorphic graphs is the labeling of the nodes and edges.

What is a planar graph?

A planar graph is a type of graph that can be drawn on a plane without any of its edges overlapping. This means that no two edges intersect each other.

How can you determine if two graphs are isomorphic?

To determine if two graphs are isomorphic, you can compare their structures, looking at the number of nodes and edges, the connections between them, and the labeling of the nodes and edges. If they have the same structure and only differ in labeling, they are isomorphic.

What are some real-world applications of these types of graphs?

Rather graphs, isomorphic graphs, and planar graphs have various applications in fields such as computer science, chemistry, and social networks. They can be used to model complex systems, analyze data, and optimize processes.

Back
Top