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:-
- $\phi$
- __
- __ __
- __ __ __
- __ __ __ __
- __ __ __ __ __
- __ __ __ __ __ __
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.