First and foremost, let's get something straight before I post my proof:(adsbygoogle = window.adsbygoogle || []).push({});

I'm not enrolled in any classes. I don't have any class money. Though my grades were strong enough for grad school, I don't think I would've made a good mathematician. I'm just not good enough. I thought I was done with mathematics for enternity because I went into web development, but recently, I've become very interested in artifical intelligence, and some things in AI uses graph theory. The graph theory explanations in most cs books Ive come acorss suck, so I decided to pick up a math book to learn. It's fun pondering again about theories and stuff, but I haven't touch a proof based math book in over 2 1/2 years. So usually when I write a proof now, i seem kinda skeptical on my work, even though everything seems logical.

Anyways I wrote this proof for a problem. I think it's right cuz everything seems logical, and I checked it with a few solutions. Though the ideas are the same, mine was worded differently and now I think what I did was wrong:

Here is the problem:

Let G and H be simple graphs which are Isomorphic. Prove that the complements G' and H' are Isomorphic (yeah I know it's an easy problem for the gurus, but it's been two and a half years. Give me a break :) ).

Note: Ive read at other places this is a iff problem, but I only did one way cuz that was the way the question was worded in my text.

Proof:

For each element x in G and the corresponding f(x) in H, the deg_{G}(x) = deg_{H}(f(x)). Now taking G' and H' implies that deg_{G'}(x) = deg_{H'}(f(x)). Therefore, since x and f(x) are adjacent to the same number of vertices in G' and H'. then for each pair of vertices x, u in G', xu is in E(G') <=> f(x)f(u) is in E(H'). So G' and H' are Isomorphic.

I'm not asking for a unique correct proof. No two minds think alike all the time. I just want verification that my proof is a valid one.

Thanks.

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# I need a second opinion on a Graph Theory proof.

Loading...

Similar Threads for need second opinion |
---|

I Second Isomorphism Theorem for Rings ... Bland Theorem 3.3.1 |

A Second derivative of a complex matrix |

I Need clarification on a theorem about field extensions/isomorphisms |

**Physics Forums | Science Articles, Homework Help, Discussion**