In directed graph G(V, E) where $V=\{P,Q,R,S,T\}$ and $E=\{PQ, RS, TP, PS, QR, PT, ST, QP, RQ, TS\}$, the vertex with maximum in-degree is _______ and vertex with maximum out-degree is _______ .

Question

Accepted Answer

The correct option is (4): S, P.

In a directed graph, the **in-degree** of a vertex is the number of edges pointing *to* it, and the **out-degree** is the number of edges pointing *away* from it. To find the maximum degrees, we must systematically calculate the in-degree and out-degree for every vertex in the set $V=\{P,Q,R,S,T\}$ based on the given edge set $E=\{PQ, RS, TP, PS, QR, PT, ST, QP, RQ, TS\}$. For a directed edge $(A, B)$, it contributes +1 to the out-degree of A and +1 to the in-degree of B. After calculating the total incoming and outgoing edges for each vertex, we find that the in-degrees are In(P)=2, In(Q)=2, In(R)=1, **In(S)=3**, and In(T)=2, making **S** the vertex with the maximum in-degree (3). The out-degrees are **Out(P)=3**, Out(Q)=2, Out(R)=2, Out(S)=1, and Out(T)=2, making **P** the vertex with the maximum out-degree (3). Therefore, the correct pair is (S, P).

The incorrect option is (1): P, S.
This option is incorrect because it confuses the roles of the two vertices by suggesting that P has the maximum in-degree and S has the maximum out-degree. P's calculated in-degree is 2, which is less than S's in-degree of 3. Conversely, S's out-degree is only 1, while P's out-degree is 3. This choice represents a common error where the maximum values are correctly found but the vertices are assigned to the wrong degree type. Students should be careful to match the vertex to the correct degree type requested in the question's order.

The incorrect option is (2): T, Q.
This option incorrectly suggests that T and Q are the vertices holding the maximum degrees. The calculated in-degree for T is 2, and the calculated out-degree for Q is 2. These values are both lower than the actual maximum in-degree (3 at S) and the maximum out-degree (3 at P). Since neither T nor Q achieves the highest degree count in the graph, they cannot be the solution pair.

The incorrect option is (3): Q, R.
This option is incorrect as the calculated degrees for Q and R are not the maximum values. Q's in-degree is 2, and R's out-degree is 2. The maximum in-degree is 3 (at S), and the maximum out-degree is 3 (at P). Furthermore, R has the minimum in-degree of all vertices (In(R)=1), making it the least connected in terms of incoming edges. This clearly rules out Q and R as the vertices with maximum degrees.