Graph Theory MCQs and Answers
Uploaded by
Aryan SinghGraph Theory MCQs and Answers
Uploaded by
Aryan Singh- Graph Theory Questions Part A
- Graph Theory Questions Part B
- Tree Representations
Common questions
Powered by AIA 3-regular graph is one where each vertex has degree 3. In a 3-regular graph with 6 vertices, the degree sequence sums to 18 (since 6 vertices × degree 3 = 18). Since each edge contributes to the degrees of 2 vertices, the number of edges is 18/2, which equals 9 .
The number of edges in the complement of a graph, G̅, is determined by subtracting the edges in the original graph from the total possible edges in a complete graph. For a graph with 10 vertices, it can have a maximum of (10×9)/2 = 45 edges. If the original graph has 10 edges, then G̅ has 45 - 10 = 35 edges .
The chromatic number of a wheel graph Wn is 3 if n is odd and greater than 3, which helps understand it as this implies a moderate complexity in coloring, requiring a minimal number of colors to ensure no adjacent vertices share the same color. For W100, which is a large wheel graph, the chromatic number is 3 .
A tree graph has n-1 edges if there are n vertices, as it is minimally connected with no cycles. Therefore, a tree graph with 10,000 vertices should have 9,999 edges. This is because each additional vertex in a tree adds a single edge, maintaining connectivity without forming a cycle .
Removing a cut-vertex from a graph results in a subgraph that is disconnected. This is because a cut-vertex is essential for holding parts of the graph together, and its removal causes one or more parts to be disconnected from the rest of the graph .
The neighborhood of a vertex in a graph is the set of vertices that are adjacent to it. For vertex 'e', the neighborhood is defined as N(e) = {c, b, f} .
A complete graph with n vertices is planar if n ≤ 4. For n > 4, the graph becomes non-planar due to the increase in the number of edges, which cannot be drawn on a plane without edges crossing .
To determine if a degree sequence is graphic, it must satisfy the Handshaking Lemma, where the sum of degrees is even, and the sequence can form a simple graph. The sequence 5, 3, 3, 3, 3, 3 is graphic as it satisfies these conditions .
Two graphs are isomorphic if they have the same degree sequence and the same number of edges, and can have their vertices relabeled to look identical. However, it's a misconception that they must look the same without relabeling or have the same number of circuits of the same length .
A complete bipartite graph K2,5 has 10 edges. In bipartite graphs, edges only connect vertices from different sets, not within the same set. Thus, edges in K2,5 are calculated as the product of the vertex counts in the two sets, resulting in 2 × 5 = 10 .
