I need a second opinion on a Graph Theory proof.

[dt666999]

First and foremost, let's get something straight before I post my proof:

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 I've 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 because 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: I've read at other places this is a iff problem, but I only did one way because 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.

 

[matt grime]

I'm not sure I see why the statement 'then for each pair of vertices x,u in G' xu is in E(G')...' has anything to do with what went before it. Normally vertex degree is a poor tool in isomorphisms of graphs.

My proof (if we're sharing) is:

xu is in E(G') iff xu not in E(G) iff f(x)f(u) not in E(H) iff f(x)f(u) in E(H'). (Actually that is overly complicated really. Def of isom: it's a bijection on vertices and xu is an edge in G iff f(x)f(u) is an edge in H, so the proof is just the negation of the definition of an isomorphism of graphs.)

Alternatively one could consider the complete graph on the vertices of G.

 

[dt666999]

I'm not sure I see why the statement 'then for each pair of vertices x,u in G' xu is in E(G')...' has anything to do with what went before it. Normally vertex degree is a poor tool in isomorphisms of graphs.

My proof (if we're sharing) is:

xu is in E(G') iff xu not in E(G) iff f(x)f(u) not in E(H) iff f(x)f(u) in E(H').

Alternatively one could consider the complete graph on the vertices of G.

Well your proof I've already saw after I wrote mine up. That's fine because I already saw all that stuff going on when thinking about writing mine up. Unforunately, I wasnt thinking about writing it like that when writing mine up.

The only reason I choose the degree is because any two sets which are isomorphic to each other must contain identical degree sequences. As a consequence, each vertex in G and the corresponding one in H must contain the same adjacent number of vertices before and after the complements are taken. Because of that, adjacency totals is preserved amongst the verticies when the complement is taken.

So for my statement "then for each pair of vertices x,u in G,' xu is in E(G')", I'm saying for any two verticies in the complement of G which constitute an edge, the corresponding vertices mapped to H' must also also contain a corresponding edge and vice versa. This is a result of the complements and adjaceny totals on the vertices in G' and H'.

Note: the u I stated in the pair is not the same vertex with x which constitiutes an edge in G. You can label that one y if you want.

Also, " x,u in G,' xu is in E(G')" is the definition for an isomorphism in my book. I've seen different books which write it differently.

 

[AUMathTutor]

Maybe I'm misreading what you're saying, but...

Two graphs can have the same degree sequence and fail to be isomorphic. I can provide a counterexample as proof if you'd like to see one.

So "they have the same degree sequence" => "they're isomorphic" is wrong. If I missed something, and particularly if this isn't what you were saying, I apologize.

 

[dt666999]

Maybe I'm misreading what you're saying, but...

Two graphs can have the same degree sequence and fail to be isomorphic. I can provide a counterexample as proof if you'd like to see one.

So "they have the same degree sequence" => "they're isomorphic" is wrong. If I missed something, and particularly if this isn't what you were saying, I apologize.

You're right. I feel like custard right now. That's what I get for quitting math. I should've not posted this and thought about the problem further. I just went back in circles with my logic.

That was on me.

Thanks for your help guys.

 

[dt666999]

Ok guys,

I have another one I worked on. I originally approached this one with a proof by contradiction. I've seen it done with a direct proof. I think all of my logic is correct, but I need a second opinion:

Problem:

If G is a simple connected graph such that diam(G) >=3, then prove that diam(G') <= 3.

For those not familiar with programming:

<= means less than or equal to
>= means greater than or equal to.

Proof:

Assume diam(G') > 3. Let M(u,v) = diam(G') where u,v are vertices in V(G'). Since u and v are not adjacent in G', they must be adjacent in G and uv is in edge in E(G). Since G is connected and diam(G) >= 3, then choosing a z in V(G) such that vz, uz is not in E(G) results in M(v, z) + M(u, z) >= M(v, u). But, M(v,z) + M(z, u) = 1 + 1 = 2 < M(v, u). So there is a contradiction and diam(G') <= 3.

 

[matt grime]

Assume diam(G') > 3. Let M(u,v) = diam(G') where u,v are vertices in V(G'). Since u and v are not adjacent in G', they must be adjacent in G and uv is in edge in E(G).

Ok so far

Since G is connected and diam(G) >= 3, then choosing a z in V(G) such that vz, uz is not in E(G)

It isn't immediately obvious that such a z exists. It does, otherwise diam(G)<3, but it would be nice to say this more clearly (i.e. say 'there exists a z such that...'

results in M(v, z) + M(u, z) >= M(v, u). But, M(v,z) + M(z, u) = 1 + 1 = 2 < M(v, u). So there is a contradiction and diam(G') <= 3.

It would be nice to explicitly show that M means distance in G' and not G. Also, this isn't really a proof by contradiction - it is entirely constructive, you've shown that either vertices u,v are adjacent in G' or the path distance is at most 2 between them - if you look you didn't actually use the assumption that diam(G')>3, but just that u and v are not adjacent in G'.

 

[dt666999]

Ok so far


It isn't immediately obvious that such a z exists. It does, otherwise diam(G)<3, but it would be nice to say this more clearly (i.e. say 'there exists a z such that...'

You sure are picky aren't you?

But I understand that the vertex I choose is not true for all t in G. I know mathematicians take their "For all", "There are some", and "There exists a unique" very serious.

It would be nice to explicitly show that M means distance in G' and not G. Also, this isn't really a proof by contradiction - it is entirely constructive, you've shown that either vertices u,v are adjacent in G' or the path distance is at most 2 between them - if you look you didn't actually use the assumption that diam(G')>3, but just that u and v are not adjacent in G'.

Matt, I'm sorry, but I've timed out one too many times trying to write this problem to the boards. Writing d_G(u,v) and d_G'(u,v) each time I want to express this will make a lot longer than typing d(u,v) and M(u,v).

My text uses d(x, y) to express the distance between any two vertices in G. Most texts I've seen use d(x,y) to denote the distance between x and y in G. I decided to use M(x, y) to denote the denote the distance for G'. Obviously the distance between vertices may not necessarily be the same in both G and G'. I thought my notation would've be obvious. I guess not.

And you stated I did not use diam(G') > 3.

diam(G') = max(ecc(u)) = M(u, v) => Path P_k between u and v such that u=w₀->w₁->w₂...->w_k=v with k>=5. Since vertices are unique in a path and path length is at least 4, u and v are not adjacent in G'.

That's how I used it, but again, it should be obvious u and v are not adjacent since M(u, v) = diam(G') > 4.

Not only that, it's not like u and v were just any two verticies in V(G'). They were two verticies in the Periphery of G.

 

[dt666999]

double post. Sorry.

 

[matt grime]

You sure are picky aren't you?

I just don't think that your original wording was optimal, and it could be phrased to make it clear what implies that such a z exists.

Matt, I'm sorry, but I've timed out one too many times trying to write this problem to the boards. Writing d_G(u,v) and d_G'(u,v) each time I want to express this will make a lot longer than typing d(u,v) and M(u,v).



My text uses d(x, y) to express the distance between any two vertices in G. Most texts I've seen use d(x,y) to denote the distance between x and y in G. I decided to use M(x, y) to denote the denote the distance for G'. Obviously the distance between vertices may not necessarily be the same in both G and G'. I thought my notation would've be obvious. I guess not.

Well, first, you can type the response into a text editor before posting, and second if you use notation without explaining what it means then that makes it hard for someone to proof read - you know M means distance in G' but you didn't tell us.

And you stated I did not use diam(G') > 3.

Sorry I if wasn't clear here - I still don't think you need to make this an assumption at all. I think your proof can be phrased in a constructive manner to show that the path length is bounded above by 3 without necessitating any assumptions. I should have phrased it better and not said 'use' but 'need to use'. Of course I might be missing something trivial.

 

[dt666999]

I just don't think that your original wording was optimal (nor grammatically correct, as it happens), and it could be phrased to make it clear what implies that such a z exists.

I guess your right. So I'll make sure to clearly stated an existence, uniqueness, and for all if its happening in a future problem.

Well, first, you can type the response into a text editor before posting, and second if you use notation without explaining what it means then that makes it hard for someone to proof read - you know M means distance in G' but you didn't tell us.

I forgot to take into account that many people here engage in research and may've potentially come across notation such as M(u, v) = diam(G') with M(u, v) not necessarily being a metric between two vertices in G'. So I'm sorry about that.

Sorry I if wasn't clear here - I still don't think you need to make this an assumption at all. I think your proof can be phrased in a constructive manner to show that the path length is bounded above by 3 without necessitating any assumptions. I should have phrased it better and not said 'use' but 'need to use'. Of course I might be missing something trivial.

But if I did it a constructive manner, then that would circle back to me approaching this problem in a direct manner, and that is not the way I initially saw to approach this problem. After adding in the additional clarifications from the previous posts, I started off with an initial condition from the contradiction assumption diam(G') > 3 and diam(G) >= 3, and ended up with the inequality M(v,z) +M(z, u) = 1 + 1 = 2 < M(v,u) which cannot be true based on the inequality M(v,z) + M(u, z) >= M(v, u).

 

[matt grime]

There is a general desire to avoid unnecessary proofs by contradiction, which is what this felt like as your original proof at no point made an explicit use of diam(G') being assumed to be more than 3, merely that u and v were not adjacent.

 

[dt666999]

There is a general desire to avoid unnecessary proofs by contradiction, which is what this felt like as your original proof at no point made an explicit use of diam(G') being assumed to be more than 3, merely that u and v were not adjacent.

Like I said, that was the way I saw it.

People have different ways of seeing things. So if you can see it with a direct proof, then congrats to you. I didn't see it that way.

I may've not used diam(G') explicitly, which is fine, but I did use it implicitly to to show that the verticies in the Periphery of G' for a Diam(G') > 4 are adjacent in G, and by logic, that should be sufficient to continue the proof.

Hey thanks for your help man, but I'm going to see if I can get other feedback from someone else.

 

[matt grime]

but I did use it implicitly to to show that the verticies in the Periphery of G' for a Diam(G') > 4 are adjacent in G, and by logic, that should be sufficient to continue the proof.

All you used was that there is not an edge between u and v in G', which is weaker than assuming diam(G')>4, though you're use of > and >= is now confusing me - you assumed diam(G')>3, not 4.

You might have seen it as a proof by contradiction, but that doesn't mean that it is - I've written many proofs with 'assume not X' only find I've actually just proven X. I'm not changing your proof - I'm just saying what I think you've proven.

I also have this niggling doubt that you've just shown diam(G')<=2, not 3 as well.

 

[dt666999]

All you used was that there is not an edge between u and v in G', which is weaker than assuming diam(G')>4, though you're use of > and >= is now confusing me - you assumed diam(G')>3, not 4.

It's called a typing mistake

You might have seen it as a proof by contradiction, but that doesn't mean that it is - I've written many proofs with 'assume not X' only find I've actually just proven X. I'm not changing your proof - I'm just saying what I think you've proven.

I also have this niggling doubt that you've just shown diam(G')<=2, not 3 as well.

Like I said, I'm just going to get an opinion from someone else. That's it. Again, thanks for your help.