UGC NET CS Practice Set 1

Explanation: R is symmetric because if |a − b| ≥ 2 then |b − a| ≥ 2. It is not reflexive since |a − a| = 0 < 2. It is not transitive: (1,3) and (3,5) are in R but |1−5|=4≥2 holds — however (3,5) and (5,3) are in R but (3,3) is not since |3−3|=0. Actually checking: (1,3)∈R and (3,1)∈R but (1,1)∉R so transitivity fails. It is not antisymmetric because (1,3) and (3,1) are both in R but 1≠3.

Explanation: The number of equivalence relations on a set of n elements equals the Bell number B(n). B(4) = 15. These correspond to the 15 ways of partitioning a 4-element set.

Explanation: This is the hypothetical syllogism. If p→q and q→r, then p→r. This is true for all truth assignments, making it a tautology. It can be verified by constructing a truth table with 8 rows.

Explanation: By De Morgan's laws for quantifiers, ¬(∀x ∃y P(x, y)) = ∃x ¬(∃y P(x, y)) = ∃x ∀y ¬P(x, y). Each quantifier flips when negation passes through it.

Explanation: A disconnected graph with n vertices has maximum edges when one component is a complete graph on (n−1) vertices and one vertex is isolated. C(9,2) = 36. Adding any more edge would require connecting the isolated vertex.

Explanation: The Petersen graph is 3-chromatic. It contains odd cycles (length 5), so it is not bipartite, hence χ ≥ 3. It can be shown that 3 colors suffice by explicit construction.

Explanation: A complete binary tree with n nodes has ⌈n/2⌉ leaves. For n = 127 (a perfect binary tree of height 6), all nodes at level 6 are leaves. The number is 2^6 = 64, which equals (127+1)/2 = 64.

Explanation: By Cayley's formula, the number of labeled spanning trees of Kₙ is n^(n−2). For K₄, this is 4^2 = 16.

Explanation: By the Master Theorem, a=2, b=2, f(n)=n. log_b(a) = 1, so f(n) = Θ(n^1) = Θ(n^(log_b a)). This is Case 2, giving T(n) = Θ(n log n).

Explanation: This is a stars-and-bars problem with each box having at least 1 ball. Place 1 ball in each box first (leaving 6 balls for 4 boxes). The count is C(6+4−1, 4−1) = C(9, 3) = 84.

Explanation: Degeneracy occurs when one or more basic variables are zero in a basic feasible solution. This can cause the simplex method to cycle, although cycling is rare in practice.

Explanation: The dual of min cᵀx s.t. Ax ≥ b, x ≥ 0 is max bᵀy s.t. Aᵀy ≤ c, y ≥ 0. The objective changes from min to max, ≥ constraints become ≤, and the variable sign restrictions are preserved.

Explanation: If a * a = e for all a ∈ G, then for any a, b: a * b = (a * b)⁻¹ = b⁻¹ * a⁻¹ = b * a. So the group is commutative (abelian). Such a group has every element of order 1 or 2.

Explanation: Write (1 + x + x²)^10 = Σ over multinomial. Substituting x = x¹ and x² terms, we need the coefficient of x⁵. Using the expansion (1+x+x²)^10 = Σ C(10,a,b,c) where a+b+c=10 and b+2c=5. The valid (b,c) pairs are (5,0),(3,1),(1,2). The sum = C(10,5)·C(5,5) + C(10,3)·C(7,1)·... This reduces to a combinatorial sum that must be computed systematically. The answer is obtained by the multinomial approach.

Explanation: K₅ has 10 edges. By Euler's formula for planar graphs, e ≤ 3v − 6 = 3(5) − 6 = 9. So at least 1 edge must be removed. Removing any single edge from K₅ gives a planar graph, so the answer is 1.

Explanation: A Boolean algebra is a complemented distributive lattice with a universal upper bound (1) and lower bound (0). All three properties — complemented, distributive, and bounded — are required.

Explanation: Each of the m elements in the domain can map to any of the n elements in the codomain independently. So the total number of functions is n × n × ... × n (m times) = n^m.

Explanation: The sum of degrees = 3+3+3+3+2 = 14, which is even. Wait — 14 is even. Let me recheck using Erdős–Gallai. Actually the sum is 14 which is even, so a graph could exist. By Erdős–Gallai: sorted (3,3,3,3,2), for k=1: 3 ≤ 1(0)+min(3,1)+min(3,1)+min(3,1)+min(2,1) = 0+1+1+1+1 = 4. 3≤4 ✓. Actually, this sequence IS graphical. The answer should be reconsidered — the sum 3+3+3+3+2=14 is even. The correct answer is that such a graph does exist.

Explanation: In the simplex method for maximization, when all coefficients (reduced costs) in the objective row are non-negative, no adjacent BFS can improve the objective. The current BFS is optimal.

Explanation: The inclusion-exclusion principle for three sets adds back the triple intersection because subtracting pairwise intersections removes elements in all three sets too many times. The formula is |A|+|B|+|C|−|A∩B|−|A∩C|−|B∩C|+|A∩B∩C|.

Explanation: Euler's theorem states that a connected graph has an Euler circuit (a closed walk visiting every edge exactly once) if and only if every vertex has even degree. Exactly two odd-degree vertices gives an Euler path (not circuit).

Explanation: A Boolean function of n variables has 2^n rows in its truth table. Each row can independently be 0 or 1, so there are 2^(2^n) distinct Boolean functions.

Explanation: The characteristic equation is x² = x + 1, giving roots φ = (1+√5)/2 and ψ = (1−√5)/2. Since |ψ| < 1, T(n) = Θ(φ^n) where φ ≈ 1.618 is the golden ratio.

Explanation: The max-flow min-cut theorem (Ford-Fulkerson) states that in a flow network, the maximum amount of flow from source to sink equals the minimum total capacity of edges whose removal disconnects source from sink.

Explanation: In a complete bipartite graph K_{m,n}, every vertex in one partition is connected to every vertex in the other. The number of edges = m × n = 3 × 4 = 12.

Explanation: The inclusion-exclusion principle is used to count elements in the union of sets. |A∪B∪C| = |A|+|B|+|C|−|A∩B|−|A∩C|−|B∩C|+|A∩B∩C| where A, B, C are sets of multiples of 3, 5, 7 respectively.

Explanation: In a totally ordered set (chain) of n elements, the only antichains are the empty set and the n singletons (since any two elements are comparable, no antichain can have ≥2 elements). So the count is n + 1 = 6.

Explanation: For the recurrence a_n − 5a_{n-1} + 6a_{n-2} = 0, the characteristic equation is x² − 5x + 6 = 0, which factors as (x−2)(x−3) = 0 giving roots 2 and 3.

Explanation: For a cycle graph Cₙ, the chromatic number is 2 if n is even and 3 if n is odd. Since 7 is odd, χ(C₇) = 3.

Explanation: By the consensus theorem, if we have XY + X'Z + YZ, the term YZ is redundant. Here X=A, Y=B, Z=C. So AB + A'C + BC = AB + A'C. The term BC is the consensus term and can be removed.