Let X and Y be the integers representing the number of simple graphs p...
Number of simple graphs possible with n labeled vertices is 2^(n(n-1)/2).
Number of simple graphs possible with n unlabeled vertices is n+1.
Number of spanning tree possible with n vertices complete graph n^(n-2)
X =8
Y = 4
X-Y=4
Therefore required answer is 4^2=16.
View all questions of this test
Let X and Y be the integers representing the number of simple graphs p...
To solve this problem, we need to understand the concepts of simple graphs, labeled and unlabeled vertices, and spanning trees.
1. Simple Graphs:
A simple graph is an undirected graph that does not contain any self-loops or multiple edges between the same pair of vertices. In simple graphs, the edges are not labeled.
2. Labeled and Unlabeled Vertices:
Labeled vertices refer to vertices that are uniquely identified or numbered. For example, if we have 3 labeled vertices, they could be represented as V1, V2, and V3. Unlabeled vertices, on the other hand, do not have any specific identification or numbering. They are simply considered as vertices without any specific labels.
3. Number of Simple Graphs:
The number of simple graphs with n labeled vertices can be calculated using the formula 2^(n(n-1)/2). In our case, we have 3 labeled vertices, so the number of simple graphs with 3 labeled vertices is 2^(3(3-1)/2) = 2^3 = 8.
4. Number of Unlabeled Graphs:
The number of unlabeled graphs with n vertices can be calculated using the formula (2^(n(n-1)/2))/n!. In our case, we have 3 unlabeled vertices, so the number of unlabeled graphs with 3 vertices is (2^(3(3-1)/2))/3! = (2^3)/6 = 8/6 = 4/3.
5. Difference between X and Y:
X represents the number of simple graphs possible with 3 labeled vertices, which is 8.
Y represents the number of simple graphs possible with 3 unlabeled vertices, which is 4/3.
So, X - Y = 8 - 4/3 = 24/3 - 4/3 = 20/3.
6. Number of Spanning Trees:
A spanning tree of a graph is a subgraph that includes all the vertices of the original graph with the minimum possible number of edges, and it must be a tree (i.e., no cycles). The number of spanning trees in a complete graph with n vertices can be calculated using the formula n^(n-2). In our case, we have N labeled vertices, which is 20/3. So the number of spanning trees would be (20/3)^(20/3 - 2) = (20/3)^18/3 = (20^18)/(3^18).
7. Final Answer:
To find the number of spanning trees possible with N labeled vertices complete graph, we substitute N = 20/3 into the formula. Calculating this value will give us the final answer, which is option 'C' (16).
In summary, the number of spanning trees possible with N labeled vertices complete graph is 16.
To make sure you are not studying endlessly, EduRev has designed Computer Science Engineering (CSE) study material, with Structured Courses, Videos, & Test Series. Plus get personalized analysis, doubt solving and improvement plans to achieve a great score in Computer Science Engineering (CSE).