Search   Memberlist   Usergroups
 Page 1 of 1 [5 Posts]
Author Message
Brendan O'Sullivan
science forum beginner

Joined: 18 Jun 2005
Posts: 48

Posted: Sun Jun 19, 2005 3:16 pm    Post subject: Bipartition

I think I have a good grasp on vertices and edges now.

Let K_2,3 have bipartition B U W where B = {a,b}, W = {x_1, x_2, x_3}.

(a) Explain why, in a spanning tree of K_2,3, there must be precisely one of
the vertices x_i joined to both a and b.

(b) How many spanning trees does K_2,3 have?

(c) How many spanning trees does K_2,100 have?
Brendan O'Sullivan
science forum beginner

Joined: 18 Jun 2005
Posts: 48

Posted: Sun Jun 19, 2005 8:37 pm    Post subject: Re: Bipartition

 Quote: Let K_2,3 have bipartition B U W where B = {a,b}, W = {x_1, x_2, x_3}. (a) Explain why, in a spanning tree of K_2,3, there must be precisely one of the vertices x_i joined to both a and b. Since you have a bipartition, no edges go from B to B, or form W to W. If each vertex in W is connected ONLY to a OR to b, that allows you to partition W into "those connected to a" and "those connected to b". So, did you have a spanning tree then? A typical spanning tree would be:

a x_1 b x_2 , there must be precisely one of
the vertices x_i joined to both a and b, as it is not possible for the tree
to be completed otherwise.

 Quote: (b) How many spanning trees does K_2,3 have? Surely you can figure this one out explicitly. The idea, of course, is to try to see a pattern in your counting, so that you can generalize for the next question: a x_1 b x_2

a x_2 b x_3
a x_1 b x_3
I get three for it, which corresponds to 3C2 = 3
 Quote: (c) How many spanning trees does K_2,100 have?

I would say the pattern would be 100 C2 = 4950

Thanks very much for your help, you are a wizard with the topic.
Arturo Magidin
science forum Guru

Joined: 25 Mar 2005
Posts: 1838

Posted: Sun Jun 19, 2005 8:40 pm    Post subject: Re: Bipartition

Brendan O'Sullivan <bos4@esatclear.ie> wrote:
 Quote: I think I have a good grasp on vertices and edges now.

Good. So these questions you are writing now, they are just
rhetorical, right? It's not like you are asking for help, since you
did not in fact ask for help. You just posted questions copied from
somewhere.

 Quote: Let K_2,3 have bipartition B U W where B = {a,b}, W = {x_1, x_2, x_3}. (a) Explain why, in a spanning tree of K_2,3, there must be precisely one of the vertices x_i joined to both a and b.

Since you have a bipartition, no edges go from B to B, or form W to
W. If each vertex in W is connected ONLY to a OR to b, that allows you
to partition W into "those connected to a" and "those connected to
b". So, did you have a spanning tree then?

 Quote: (b) How many spanning trees does K_2,3 have?

Surely you can figure this one out explicitly. The idea, of course, is
to try to see a pattern in your counting, so that you can generalize
for the next question:

 Quote: (c) How many spanning trees does K_2,100 have?

So... What have you done so far?

--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes")
======================================================================

Arturo Magidin
magidin@math.berkeley.edu
Brendan O'Sullivan
science forum beginner

Joined: 18 Jun 2005
Posts: 48

Posted: Mon Jun 20, 2005 3:14 pm    Post subject: Re: Bipartition

"Arturo Magidin" <magidin@math.berkeley.edu> wrote in message
news:d96t77\$dm3\$1@agate.berkeley.edu...

Thanks Arturo,
I think that will keep me busy for a while!
Brendan
Arturo Magidin
science forum Guru

Joined: 25 Mar 2005
Posts: 1838

Posted: Mon Jun 20, 2005 5:08 pm    Post subject: Re: Bipartition

Brendan O'Sullivan <bos4@esatclear.ie> wrote:
 Quote: Let K_2,3 have bipartition B U W where B = {a,b}, W = {x_1, x_2, x_3}. (a) Explain why, in a spanning tree of K_2,3, there must be precisely one of the vertices x_i joined to both a and b. Since you have a bipartition, no edges go from B to B, or form W to W. If each vertex in W is connected ONLY to a OR to b, that allows you to partition W into "those connected to a" and "those connected to b". So, did you have a spanning tree then? A typical spanning tree would be: a x_1 b x_2 , there must be precisely one of the vertices x_i joined to both a and b, as it is not possible for the tree to be completed otherwise.

Just asserting something is seldom a proof. Just repeating what you
are asked to prove with conviction is seldom convincing,
either. Saying something is "typical" doesn't prove anything. What if
"typical"? What proof do you have that every spanning tree will "look
like" what you have written down?

Without a satisfactory answer to all those questions, what you have is
not a proof, just bluster.

Why not complete what I wrote, or come up with some full proof of your
own?

Suppose you have a connected bipartite graph G, with two parts B and
W; |B|=2 and |W|=3. We want to prove that in a spanning tree for G,
there must be at least one vertex in W which is adjacent to both
vertices in B.

Given a spanning tree for W, we can divide W into three distinct sets:

W_a = { w in W : w is only adjacent to a in the tree}
W_b = { w in W : w is only adjacent to b in the tree}
W_{ab} = {w in W: w is adjacent to both a and b in the tree}

(since it is a spanning tree, you cannot have a w in W which is
adjacent to neither a nor b, because then it would be an isolated
point).

Since T is connected, there must be a path from a to b. From a you can
only go to a w in W_a or a w in W_{ab}. From a w in W_a you can only
go to a. So a path from a to b must start at a, go to a vertex in
W_{ab}, and then go to b; hence W_{ab} must be nonempty, as was to be
shown.

 Quote: (b) How many spanning trees does K_2,3 have? Surely you can figure this one out explicitly. The idea, of course, is to try to see a pattern in your counting, so that you can generalize for the next question: a x_1 b x_2 a x_2 b x_3 a x_1 b x_3 I get three for it, which corresponds to 3C2 = 3

I'm not even sure what "a x_1 b x_2" is supposed to be. Not a spanning
tree, at any rate (where is x_3?)

There are plenty more than 3. You can have x_1 adjacent to
both a and b, and both x_2 and x_3 adjacent to b; or both adjacent to
a; or x_2 to a and x_3 to b; or x_2 to b and x_3 to a. That gives me
FOUR spanning trees already, and I haven't considered what happens if
the vertex adjacent to both a and b is x_2 instead of x_1.

Also: just because 3 happens to be equal to (3 choose 2) does not
necessarily mean that the correct answer will always be (n choose 2)
for K_{2,n}. How do you make trees correspond to ways of choosing two
out of 3? 3 is also equal to (3 choose 1), so why not (n choose 1) as
the general case?

Let's go back to the partition above. We have shown that W_{ab} must
have at least one element. I claim that it has at MOST one element.
For, supposw that w,w' are elements of W_{ab}. Then there is a path
from a to w, from w to b, from b to w', and from w' to a, giving a
cycle. This is impossible in a spanning tree, so W_{ab} must have at
most 1 element.

So, to construct a spanning tree, first we must choose the 1 element
in W_{ab}. The number of ways to make that choice is (3 choose 1).

Having chosen the one and only one vertex of W which will be adjacent
to both a and b, each of the remaining 2 vertices will be adjacent
to either a or b. They can be adjacent to either, and the choice is
completely free. So we have two possibilities for each of the 2
vertices, giving 2^{2} = 4 possibilities.

Thus, there are 4 spanning trees for EACH choice of which vertex in W
will be adjacent to both a and b, and there are 3 choices of which
vertex that will be. That gives me (3 choose 1)*2^2 = 12 spanning
trees.

 Quote: (c) How many spanning trees does K_2,100 have? I would say the pattern would be 100 C2 = 4950

You'd say wrong.

Again, as above, we can choose any ONE vertex in W (which this time
has 100 elements) to be adjacent to both a and b. After that choice,
the remaining 99 vertices can each be made adjacent to either a or b
(but not both). So, how many spanning trees does K_{2,100} have, then?

--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes")
======================================================================

Arturo Magidin
magidin@math.berkeley.edu

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [5 Posts]
 The time now is Tue Nov 21, 2017 6:09 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters