retagged by
2,722 views

2 Answers

Best answer
1 votes
1 votes

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..

edited by
0 votes
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 .

Related questions

2 votes
2 votes
2 answers
3
shivani2010 asked Jun 12, 2016
4,253 views
An undirected graph is Eulerian if and only if all vertices of G are of the sum of the degrees of all nodes isA. Same degreeB. ODD degreeC. Need not be ODDD. ...
0 votes
0 votes
2 answers
4
yuuchan asked Jul 22, 2023
475 views
If G is a complete bipartite graph with n vertices (n >= 2) and minimum number of edges, then matching number of G is ____1n-1⌊n/2⌋⌈n/2⌉