For such problems, we need to check what is the pattern by taking extreme values.
Let n=4 elements which is repn by a set S= {a,b,c,d} .
So G =< P(s) , E> where P(s) represent the vertices of G and E is the set of edges of G.
Vertices of G = P(s) = {ϕ,{a},{b},{c},{d},{a,b},{a,c},{a,d},{b,c},{b,d},{c,d}{a,b,c},{b,c,d},{a,b,d},{a,c,d},{a,b,c,d}} .
Total no of vertices = 2^4 =16
Edges of G = Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.
Degree of Vertices D(v) of G
D(ϕ) = D({a})=D({b})=D({c}),=D({d}) = Degree of a vertex of G which having 0 or 1 element = 0
D({a,b})=D({a,c})=D({a,d})=D({b,c})=D({b,d})=D({c,d}) = Degree of a vertex of G which having 2 elements = 4 (with self loop) ,
See the Vertex {a,b} is incident with {a,b} ,{a,b,c}, {a,b,d}, {a,b,c,d} so the degree of Vertex {a,b} is 4.
D({a,b,c})=D({a,c,d})=D({a,b,d})=D({b,c,d}) = Degree of a vertex of G which having 3 elements = 6,
See the Vertex {a,b,c} is incident with {a,b},{a,c},{b,c} ,{a,b,d} ,{a,c,d}, {b,c,d} so the degree of Vertex {a,b,c} is 6.
D({a,b,c,d})= Degree of a vertex of G which having 4 elements = 6,
See the Vertex {a,b,c,d} is incident with {a,b},{a,c},{b,c} ,{b,d} ,{a,d}, {c,d} so the degree of Vertex {a,b,c,d} is 6.
When we increase the n values we see that the vertex of G which has 3 or 4 elements have the max Degree.
Generalization: Let the vertex of G which having k elements. Now, as per the given condition, it can have edges to all vertices having two common elements (exactly 2 commons). So, we can choose the 2 common elements in ^{k}C_{2 }ways. Now, for each of these 2 pair of elements, it can have an edge to a vertex containing n−k elements + the 2 common elements. This will be equal to 2^{n−}^{k}possible subsets as the 2 common elements must always be present and other k elements must always be absent. So, we get the degree as
^{k}C^{2}.2^{n−k}
See the table for clear understanding,
Vertex of G having k elements of n |
Degree of Vertex of G having k elements of n |
Degree at n=6 ,n=7,n=8 |
k=0 ,vertex ϕ |
0 |
0,0,0 |
k=1 |
0 |
0,0,0 |
k=2 |
C(2,2).2^{(n-2)} =2^{(n-2) } |
16,32,64 |
k=3 |
C(3,2).2^{(n-3)} = 3.2^{(n-3)} |
24,48,96 |
k=4 |
C(4,2).2^{(n-4)} = 3.2^{(n-3)} |
24,48,96 |
k=5 |
C(5,2).2^{(n-5)} = 10.2^{(n-5)} |
20,40,80 |
k=k |
C(k,2).2^{(n-k)} |
C(k,2).2^{(n-k)} put n |
k=n |
C(n,2).2^{(n-n)} = C(n,2) |
15,21,28 |
We can clearly see that Degree of Vertex of G having k =3 or k=4 elements of n having the max value which is 3.2^{(n-3)}.
The correct answer is (c)2^{(n-3)}⨉3