I am given a tree T with n vertices. When we get rid of edve u,v we get 2 components of the tree  1 containing vertex u, and the other containing vertex v.
n_u will denote number of vertices in the component where u is, and n_v will be the number of vertices where v is.
Prove that when n_u = n_v, then the closeness of vertices v and u is the same.

So, i have attempted to do it, and i have drawn a simple tree that satisifies the condition n_u = n_v and i have found that indeed the closeness of vertices n and v is the same.
e.g
A  u  v  C  D

B 
So in this case:
Closeness of vertex u would be: (1/1 + 1 + 2 + 3) = 1/7
Closeness of vertex v would be: (1/1+2+2+2) = 1/7
So, i can demostrate that it holds on a simple example, but how would i go about proving it for any case.
I dont want you to give me fullblown solution but maybe the steps i need to think about etc.
Help with a proof.
Page 1 of 13 Replies  709 Views  Last Post: 30 November 2011  09:05 AM
Replies To: Help with a proof.
#2
Re: Help with a proof.
Posted 30 November 2011  07:59 AM
Quote
So, i have attempted to do it, and i have drawn a simple tree that satisifies the condition n_u = n_v and i have found that indeed the closeness of vertices n and v is the same.
e.g
e.g
A  u  v  C  D  B 
That's a bit easier to read. I'm not sure I know what you mean by the "closeness" of a vertex. Could you define it?
Quote
So in this case:
Closeness of vertex u would be: (1/1 + 1 + 2 + 3) = 1/7
Closeness of vertex v would be: (1/1+2+2+2) = 1/7
Closeness of vertex u would be: (1/1 + 1 + 2 + 3) = 1/7
Closeness of vertex v would be: (1/1+2+2+2) = 1/7
I think you've bollixed your parens. Do you mean this?
1/(1+1+2+3) = 1/7
1/(1+2+2+2) = 1/7
#3
Re: Help with a proof.
Posted 30 November 2011  08:02 AM
What have you done so far? What is your good faith effort on your own project before asking us to do it for you?
Reminder to all: This is course homework. We do NOT provided completed solutions for homework. We can help the OP understand specific concepts they are having trouble with or specific errors they don't understand.
Of course they have to tell us the specific errors first, and not just "Can you help me with my homework, its due soon."
The stages of asking for homework help on a forum
Reminder to all: This is course homework. We do NOT provided completed solutions for homework. We can help the OP understand specific concepts they are having trouble with or specific errors they don't understand.
Of course they have to tell us the specific errors first, and not just "Can you help me with my homework, its due soon."
The stages of asking for homework help on a forum
tlhIn`toq said:
The three different kinds of rookie posters on DIC.
Spoiler
Page 1 of 1