Help with a proof.

Page 1 of 1

3 Replies - 476 Views - Last Post: 30 November 2011 - 09:05 AM

#1 studentforlife

Reputation: 0
• Posts: 1
• Joined: 19-December 10

Help with a proof.

Posted 29 November 2011 - 07:55 PM

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 full-blown solution but maybe the steps i need to think about etc.

Is This A Good Question/Topic? 0

Replies To: Help with a proof.

#2 jon.kiparsky

• Pancakes!

Reputation: 7562
• Posts: 12,680
• Joined: 19-March 11

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
```      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

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 tlhIn`toq

Reputation: 5432
• Posts: 11,643
• Joined: 02-June 10

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

tlhIn`toq said:

The three different kinds of rookie posters on DIC.

Spoiler

#4 jon.kiparsky

• Pancakes!

Reputation: 7562
• Posts: 12,680
• Joined: 19-March 11

Re: Help with a proof.

Posted 30 November 2011 - 09:05 AM