Please give an easy solution


#1

Let S be a set of n elements {1,2,…,n} and G a graph with 2^n vertices, each vertex corresponding to a distinct subset of S. Two vertices are adjacent iff the symmetric difference of the corresponding sets has exactly 2 elements. Note: The symmetric difference of two sets R1 and R2 is defined as (R1∖R2) ∪ (R2∖R1)

Every vertex in G has the same degree.

(i)What is the degree of a vertex in G?

(i)How many connected components does G have?


#2

S=1,2,3,4,5,6…nS=1,2,3,4,5,6…n
Let us assume any two subset S1S1 and S2S2. We can simply assume n(S1∩S2)=0n(S1∩S2)=0 to consider the disconnected sets if we want.
image

Now there are three cases in which (S1∖S2)∪(S2∖S1)Or,(S1⊕S2)(S1∖S2)∪(S2∖S1)Or,(S1⊕S2) has only 22 element.
image

  1. Both green shaded area has one element each and in this case sizes of S1S1 and S2S2 are same.
    2 .The green area of S1S1 contains 22 element and the green area of S2S2 contains none. In this case size of S1S1 is 22 more than that of S2S2.
    3 .The green area of S2S2 contains 22 element and the green area of S1S1 contains none. In this case size of S2S2 is 22 more than that of S1S1.

So, if we are only interested in a particular set vertex corresponding to set S1S1 of size =m=m, then S1S1 is connected to three types of set vertices as shown below. We will use the words “set” and “vertices” synonymously.
image
In this above image, we have considered m≥2m≥2. The cases for m=1 and m=0m=1 and m=0 will be discussed later.

Now, what we need to find is the no of set vertices in each of the above three types and sum them up to get the degree of the vertex corresponding to the set S1S1.

For simplicity let us assume S={1,2,3,4,5,6,7}S={1,2,3,4,5,6,7} and set S1={1,2,3,4}S1={1,2,3,4}. Our interest will be to find S2S2 such that vertices corresponding to S1S1 and S2S2 are connected.

CASE 1 :
If we try to find another set S2S2 having 44 elements and satisfying constraint n(S1⊕S2)=2n(S1⊕S2)=2, then we will see that no of such set S2S2 is 4⋅(7−4)4⋅(7−4). Or in general if S1S1 is an mm element set then no of such S2S2 sets with constraint n(S1⊕S2)=2n(S1⊕S2)=2 will be equal to m⋅(n−m)m⋅(n−m).
CASE 2 :
S1S1 contains 44 element and If we try to find S2S2 where S2S2 contains 22 elements and satisfying constraint n(S1⊕S2)=2n(S1⊕S2)=2, then no of such S2S2 will be 4C24C2 or in general, for mm element set S1S1, we have mC2mC2 no of S2S2 type sets all with (m−2)(m−2) size.
CASE 3:
S1S1 contains 44 element and If we try to find S2S2 where S2S2 contains 66 element and satisfying constraint n(S1⊕S2)=2n(S1⊕S2)=2, then no of such S2S2 sets will be 3C23C2 or (7−4)C2(7−4)C2. In general, with S1S1 being mm element set, then (n−m)C2(n−m)C2 no of S2S2 sets will be possible

=m⋅(n−m)+(m2)+(n−m2)=m⋅n−m2+m22−m2+(n−m)⋅(n−m−1)2=m⋅n−m2+m22−m2+n⋅(n−1)2−n⋅m2−n⋅m2+m22+m2=n⋅(n−1)2=(n2)
This result is independent of mm for m≥2m≥2 and m≤nm≤n.

For m=0m=0 and m=1m=1 also we can show that degree of 00 and 11 size set vertices is nothing but nC2nC2 only. (fairly straight forward cases).

So we can conclude that every vertex has the same degree and the degree is nC2nC2.

image

i.e.for m≥2m≥2 if mm is even the S1S1 is connected to only even cardinality type of sets (at least one) or if mm is odd then S1S1 is connected to only odd cardinality type of sets (at least one). By this, we can almost say that there are two connected components in the graph.

But there is little more argument before we can proceed and have a valid proof.

if m=0m=0 then S1=ϕS1=ϕ, Then S1S1 will be connected to all m=2m=2 type of sets or 22 cardinality sets.

if m=1m=1 then S1S1 will be one of all 11 element sets, Then S1S1 will be connected to all other 11 cardinality sets and at least one 33 cardinality set.

We can argue that, one mm (even) cardinality set is at least connected to one (m−2)(m−2) cardinality set. That particular (m−2)(m−2) cardinality set is at least connected to one (m−4)(m−4) cardinality set and so on till ϕϕ set vertex. There for all even cardinality sets are connected to ϕϕ directly or indirectly.

A similar argument holds for odd cardinality set vertices till we reach some 11 cardinality set. Moreover all 11 cardinality sets are connected.

Therefore we have a situation now that all even cardinality sets form one connected component and all odd cardinality set form another component.

For example : n=4n=4 :

image


#3

I read this solution before , please give other than this solution