edited by
493 views
8 votes
8 votes
$S = \{ a_1, a_2, a_3 , \dots , a_n \}$ and $X$ and $Y$ are subsets of $S,$ where each subset represents one vertex in a graph $G$. If number of elements in $(X\setminus Y) \cup  (Y\setminus X) = 3,$ then there is an edge between the corresponding vertices for $X$ and $Y$. Given number of vertices, $n = 6,$ the degree of a vertex corresponding to a $3$ element subset is ________.

Note: The symmetric difference of two sets $z_1$ and  $z_2$ is defined as $(z_1 \setminus z_2) \cup (z_2 \setminus z_1)$
edited by

2 Answers

Best answer
8 votes
8 votes

S = { a1, a2, a3 , ............, an }, where each subset of S represent one vertex in G. So there will be 2^n vertex in G. Let X and Y be two subset of S. Then there will be an edge between X and Y iff n(X - Y) $\cup$ n(Y - X) = 3.

Here n = 6 and We need to find out the degree of a vertex having three element. Let say A = {a1, a2, a3} be a vertex.
1. A will be connected to Ø. Because (A - Ø) = A and (Ø - A) = Ø. So A $\cup$ Ø = A. And n(A) = 3.

2. For a set containing 1 element Say B, If element of B is also present in A. Then n(A - B) = 2 and n(B-A) = 0. So there will not be any edge. If element of B is different than element of A. Then n(A - B) = 3 and n(B - A) = 1. So No edge.

3. For a set containing 2 element Say B. If both the element of B are not the element of A. Then n(A - B) = 3 and n(B - A) = 2. No edge.
If one element of B is present in A also then n(A - B) = 2 and n(B - A) = 1. So there will be an edge. Now how many such set are possible? First we need to select one element from set A then any of them a4, a5, a6 can be present as second element. So 3C1 * 3C1 = 9.
If both element of B is present in A then n(A - B) = 1 and n(B - A) = 0. No edge.

4. For a set containing 3 element  say B.
Do similar approach as we have for set containing 2 element. You will find that there will be no edge.

5. For a set containing 4 element say B.
In this there will be an edge when B contain 2 element of A. So 3C2 * 3C2 = 9.

6. For a set containing 5 element, you find there is no edge.

7. For a set containing 6 element which is {a1,a2, a3, a4, a5, a6} there will be an edge.

So total = 1 + 9 + 9 + 1 = 20

selected by
0 votes
0 votes

Let S = {a,b,c,d,e}.

Let the three element subset be {a,b,c}

The symmetric difference = (X∖Y)∪(Y∖X) = (X ∪ Y) - (X  ∩ Y). I actually use the bolded formula, ie, union minus intersection.

 

We gotta find the degree of {a,b,c} — which is nothing but a vertex.

All the other vertices possible have the template:-

  1. $\phi$
  2. __
  3. __ __
  4. __ __ __
  5. __ __ __ __
  6. __ __ __ __ __
  7. __ __ __ __ __ __

 

Let's see.

1. {a,b,c} union $\phi$ - {a,b,c} intersection $\phi$ = {a,b,c}. So 1 edge.

 

2. No matter which symbol you put here, whether a familiar one, ie, a or b or c; or a new one, ie, d or e or f — symmetric difference isn't two.

Let me define the word "familiar" = a or b or c.
"new" = d or e or f.

 

3. We have two places here. Put a "new" and a "familiar" together, and we get symmetric difference = 3.

So, 3 news and 3 familiars = 9 combos.

=> Connected to 9 vertices, hence 9 edges

 

4. Nope. No combination of news and familiars generate symmetric difference 3. (Just have to try one combo for each)

 

5. Two news, two familiars would generate symmetric difference = 3.

So, $3C2 * 3C2 = 9$. 9 edges.

 

6.Nope,

 

7. 3 news and 3 familiars, ie, the only possible set {a,b,c,d,e,f} gives symmetric difference 3 with {a,b,c}. So, 1 edge.

 

Total = $20$ edges. = Degree.

Answer:

Related questions

5 votes
5 votes
2 answers
2
Bikram asked May 24, 2017
714 views
Let $G$ be a graph of order $8$ in which every vertex has equal degree $D$. In order to guarantee that $G$ is connected, the minimum value of $D$ must be ____________
5 votes
5 votes
2 answers
3
Bikram asked May 24, 2017
562 views
Let $S$ be the set $\{1,2,3, \dots ,8\}$. Let $n$ be the number of sets of two non-empty disjoint subsets of $S$. The value of $n$ is _______.
5 votes
5 votes
1 answer
4
Bikram asked May 24, 2017
475 views
Total number of ways we can fill a $4 \times 4$ matrix by $0$ and $1$’s such that every row and column contains odd no of $0$'s and $1$'s is ________.