Difficult problem for isomorphism in graph

ilovebillu · #1 $Old$ November 3rd, 2009, 11:49 AM

Let G10 be a simple graph of 10 vertices, and G10' its complement. As we know, the relationship between 10G and 10G is as follows: (1) they have the identical set of vertices; (2) two distinct vertices are adjacent in G10' if, and only if, they are not adjacent in 10G. Prove that 10G cannot be isomorphic to G10'.

Please help!!!! (G10 means G with a subscript of 10)

Plato · #2 $Old$ November 3rd, 2009, 12:00 PM

Quote:

Originally Posted by ilovebillu $View Post$

Let 10G be a simple graph of 10 vertices, and 10G its complement. As we know, the relationship between 10G and 10G is as follows: (1) they have the identical set of vertices; (2) two distinct vertices are adjacent in 10G if, and only if, they are not adjacent in 10G. Prove that 10G cannot be isomorphic to 10G.

Please reread this post. You have used 10G to name two different graphs have you not?
Did you perhaps mean 10C for the complement?
Please edit the post to make corrections.
Or explain what is meant.

ilovebillu · #3 $Old$ November 3rd, 2009, 12:16 PM

Ooops... sorry..yeah did the corrections

Plato · #4 $Old$ November 3rd, 2009, 01:14 PM

Here is a big hint.
The union of a graph and its complement is a complete graph.
A complete graph of order ten has forty-five edges.