CS Free MCQ Bank

[ Option B ]

We use the Handshaking Theorem, which states that the sum of the degrees of all vertices in an undirected graph equals twice the number of edges:
Sum of degrees of all vertices=2×Number of edges
Here, E=31. So,
Sum of degrees = Sum of degrees=2×31=62
The given condition is that each vertex has degree at least 3. Now, let the number of vertices be n. Then, Sum of degrees ≥ 3n. We already know the exact sum is 62, so, 3n ≤ 62.
Finally solve for n, n ≤ 62/3 = 20.66. Since the number of vertices must be an integer, the maximum possible number of vertices is 20.

[ Option D ]

A Spanning Tree of a graph is a subgraph that includes all the vertices of the graph and is connected without forming any cycles. For any connected graph with V vertices, a tree structure must have exactly V-1 edges to remain connected and acyclic.

[ Option C ]

[ Option B ]

In graph theory, a graph is made up of a set of nodes, which are technically called vertices, and a set of line segments that connect pairs of these nodes, which are called edges.
Vertices represent the objects or points in the graph, while edges represent the connections or relationships between them.

[ Option D ]

A Simple Graph is a type of graph that does not contain any parallel edges (multiple edges) or self-loops (an edge from a vertex to itself). Each edge in a simple graph connects two distinct vertices, and there can be at most one edge between any pair of vertices.

[ Option C ]

In an adjacency matrix, we represent a graph using a two-dimensional array of size n×n, where n is the number of vertices. Each row and column correspond to a vertex, and the value stored in a cell tells us whether an edge exists between two vertices.

If the graph is weighted, the cell stores the weight instead of just 0 or 1. Since the matrix always needs space for n² entries, the space complexity is O(n²). This representation can be used for directed or undirected graphs as well as weighted or unweighted graphs.

The only drawback is that it uses more memory for sparse graphs, but it provides quick access to check if an edge exists between two vertices.

[ Option B ]

Breadth First Search (BFS) explores a graph level by level, meaning it visits all the neighboring vertices of a node before moving to the next level. To achieve this order, BFS uses a Queue, which follows the First In First Out (FIFO) principle. 
Depth First Search (DFS), on the other hand, explores a graph by going as deep as possible along one path before backtracking. This behavior is naturally supported by a Stack, which follows the Last In First Out (LIFO) principle.

[ Option C ]

In an undirected graph, each edge connects two vertices and contributes 1 degree to each of its end vertices. Therefore, every edge adds a total of 2 to the sum of degrees of all vertices. 
If the graph has e edges, the total sum of the degrees of all n vertices becomes 2e. This result is known as the Handshaking Theorem in graph theory.

[ Option A ]

An Isolated Vertex in a graph is a vertex that has no edges connected to it. The degree of a vertex is defined as the number of edges connected to that vertex. Since an isolated vertex has no connecting edges, its degree is 0.

[ Option B ]

In graph theory, a Complete Graph is a simple graph in which every pair of distinct vertices is connected by an edge.

• A complete graph is highly connected and contains cycles.
• Every vertex is connected to all other n−1 vertices, so its degree is n−1.
• The total number of edges in a simple complete graph is given by (n(n−1))/2.

[ Option A ]

In any graph, the sum of the degrees of all vertices is always even because each edge contributes 2 to the total degree count. As a result, vertices with odd degree must occur in pairs so that their total contribution is even.

[ Option A ]

In a Regular Graph, every vertex has the same degree d, meaning each of the n vertices is connected to d edges. If we add the degrees of all vertices, the total becomes n*d.
However, each edge is counted twice in this total. Therefore, to get the actual number of edges, we divide by 2. 
Hence, the number of edges in a regular graph with n vertices and degree d is nd/2.

[ Option D ]

Graph traversal algorithms are specifically methods used to visit all nodes of a graph, such as:

• DFS (Depth First Search) Using Stack.
• BFS (Breadth First Search) Using Queue.

[ Option B ]

A Walk in a graph is a sequence of vertices and edges where each edge connects the previous vertex to the next one. It can repeat vertices or edges, there is no restriction.

• Open Walk, a walk is said to be open if it starts and ends at different vertices.
• Closed Walk, a walk is closed if it starts and ends at the same vertex.

In graph theory, a Cycle is a closed walk, meaning it starts and ends at the same vertex, and no other vertices or edges are repeated except the first and last vertex being the same.
A Circuit is indeed a closed walk (starts and ends at the same vertex) where no edge is repeated. Vertices may repeat, but edges do not.