Reply
Sun 11 Sep, 2005 05:09 pm
My problem states
If a graph G has n vertices all of which but one have odd degree, how many vertices of odd degree are there in The complement of G.
I am also supposed to prove it.
I've drawn a few examples and they have lead me to believe that number of vertices of odd degree in the complement is the same as the number in G, however, I don't know how to go about proving it.
Any help would be appreciated.
Thanks
Ooh, it's been a while, but here goes.
You know that G has an even number of odd vertices so say G is of size 2n+1.
Take any odd vertex v and let its degree be 2p+1. Then its degree in G complement is (2n+1) - (2p+1) - 1 (itself). So the degree of v in G complement is 2(n-p) -1 which is odd. Do the same for the even vertex and you get similar results.
thanks
Thanks, that makes sense. I'm just learning this, and the book is not very clear on some of it's applications.
Thanks again
Ernie
No problem, it was one of my favorite subects.
Stumble It!
Tweet This
Bookmark on Delicious
Share on Facebook
Share on MySpace