GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
174 views
Consider the graph G whose vertices are 4 element subsets of the set {1, 2, 3…10} with two vertices adjacent if and only if their intersection is empty. Then the number of edges does G have _______
asked in Graph Theory by Veteran (13.1k points)   | 174 views

2 Answers

+1 vote
Best answer

Number of vertices of the graph = No of 4 element subsets of 10 element set

                                                = 10C4

Now it is given :

Two vertices are adjacent iff they are disjoint subsets.

Now for disjointedness , it is necessary that the vertex should be adjacent iff the adjacent vertex contains no number in the subset represented by it which is in the given vertex representing the number ..

e.g. say we have a vertex for {1,2,3,4}  , then there will not be an edge from it to {1,4,5,6} as 1 is common..

So in short for adjacency (to have an edge) we have only such vertices whose labels will be selected from rest of the 6 vertices..

So say we have taken the vertex {1,2,3,4} we can have a vertex representing subset which have 4  numbers ranging from 5 to 10 thus only 6 options and hence which can be done in 6C4  =  15 ways in order to have an edge in between and hence incident on vertex labelled {1,2,3,4}

This is nothing but a degree of a single vertex ..So degree of vertex = 15

This will be true for all vertices 

So applying handshaking theorem , we have :

         2 e   =   15 + 15 ...............10C4 times [As number of vertices = 10C4]

==>   2 e   =    (15 * 10 * 9 * 8 * 7)  / 24

==>   e      =    15 * 5 * 3 * 7

==>   e      =     1575

 

Thus the given graph contains 1575 edges..    

For directed graph however it will be 3150 edges as say we have edge from vertex 1 to vertex 2 and vertex 2 to vertex 1 ..So both are considered to be different edges in case of directed graph and one and the same edge in case of undirected graph..By default we take undirected graph..

answered by Veteran (66.3k points)  
edited by
can you explain 6c4 logic again?

i understood that for ex ,if the subset is {1,2,3,4} then it cannot form edge with any vertex conatining 1,2,3 or 4 but could'nt understand 6C4 logic..

thankyou
i think i got your point,by 6C4 u mean for a subset,it has only 6 options and from those 6 options 4 element subset can be chosen in 6C4 ways..am i correct??
Ya exactly..:)
2e = 3150.

=> e = 3150/2 ??

i just noticed that there is some mistake in the calculation 

2e = 15 * 10C

2E= 15 * 10 * 9 * 8 * 7 /24

e = 15 * 10 * 9 * 8 * 7 /48

e= 15 * 10 * 9 * 7 /6

e = 3150 / 2

Corrected @Akriti sood..Plz check..:)
yes..:-)
0 votes
No of subsets(Vertices) with 4 elements = C(10,4)

Degree of each vertex = C(6,4).

Total degrees = C(10,4)*C(6,4).

Total edges = C(10,4)*C(6,4)/2 .
answered by Loyal (3.2k points)  


Top Users May 2017
  1. akash.dinkar12

    3598 Points

  2. pawan kumarln

    2314 Points

  3. Bikram

    1958 Points

  4. Arjun

    1942 Points

  5. sh!va

    1682 Points

  6. Debashish Deka

    1296 Points

  7. Devshree Dubey

    1282 Points

  8. Arunav Khare

    1122 Points

  9. Angkit

    1072 Points

  10. LeenSharma

    1028 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 29 - Jun 04
  1. Arjun

    292 Points

  2. Arunav Khare

    246 Points

  3. Rupendra Choudhary

    116 Points

  4. Arnab Bhadra

    108 Points

  5. pawan kumarln

    108 Points


22,912 questions
29,252 answers
65,411 comments
27,750 users