Discrete Mathematics · End Term · May 2026 · AN

The shared elements of {1,3,5} and {1,2,3} are 1 and 3. Symmetric difference keeps only elements appearing in exactly one set: 5 from the first and 2 from the second. Hence \(A\oplus B=\{2,5\}\). Set order is irrelevant. **Answer: B.** A: **Incorrect:** These are precisely the shared elements, which symmetric difference excludes. B: **Correct:** Contains the two elements present in exactly one set. C: **Incorrect:** Omits 2 from the second set's exclusive part. D: **Incorrect:** Omits 5 from the first set's exclusive part.

Symmetric difference includes either set's elements but removes the overlap: \(A\oplus B=(A\cup B)\setminus(A\cap B)\). Equivalently combine the disjoint exclusive parts: \((A\setminus B)\cup(B\setminus A)\). These descriptions are valid for arbitrary sets, not only disjoint ones. **Answer: C, D.** A: **Incorrect:** Adding the intersection back to the union leaves the entire union, including shared elements. B: **Incorrect:** The intersection of union and intersection is just A∩B, the shared region. C: **Correct:** Removes the shared region from the union. D: **Correct:** Unites the two exclusive regions. E: **Incorrect:** The two exclusive regions are disjoint, so their intersection is always empty.

Let H be \((\forall p\,B(p))\land(\exists q\,C(q))\), and K be \(\exists j\,L(j)\). The expression is \(\neg(H\Rightarrow K)\), which equals \(H\land\neg K\). Negating the existential gives \(\neg\exists j L(j)\equiv\forall j\neg L(j)\). Therefore the result is \((\forall p B(p))\land(\exists q C(q))\land(\forall j\neg L(j))\). The antecedent is retained, not negated. **Answer: D.** A: **Incorrect:** Negates the antecedent terms and leaves the consequent existential unnegated. B: **Incorrect:** Uses disjunction and negates antecedent quantifiers incorrectly for a negated implication. C: **Incorrect:** Uses disjunction of negated antecedent terms rather than retaining the whole antecedent. D: **Correct:** Correctly combines the original antecedent with the negated consequent.

The proof assumes both the hypothesis (3n+2 is odd) and the negation of the conclusion (n is even). Writing n=2k gives \(3n+2=6k+2=2(3k+1)\), which is even, contradicting the assumption that it is odd. Assuming a statement and the opposite of its conclusion and deriving an inconsistency is proof by contradiction. **Answer: C.** A: **Incorrect:** A direct proof would proceed from the hypothesis without assuming the conclusion false. B: **Incorrect:** A contraposition proof would start only from n even and prove 3n+2 even, without also assuming the original odd hypothesis. C: **Correct:** The joint assumptions lead to the odd/even contradiction. D: **Incorrect:** Proof by contradiction is explicitly one of the choices.

The set contains positive-integer pairs whose sum is even, meaning both entries have the same parity. Starting from (1,1), adding 2 to either coordinate or adding 1 to both preserves this property. These rules also generate every allowed pair: for an odd-odd pair, independently add even increments to (1,1); for an even-even pair, first reach (2,2) and then add even increments. Thus (a+2,b), (a,b+2), (a+1,b+1) are the required rules. **Answer: C.** A: **Incorrect:** Only swapping/repeating does not generate all pairs and (a,a+b) can change the parity condition. B: **Incorrect:** Adding 1 to just one coordinate makes the sum odd. C: **Correct:** Preserves positivity and even sum and generates both same-parity cases. D: **Incorrect:** The third rule adds 1 to only one coordinate and leaves the set.

To avoid receiving any fortune four times, each of the 213 types can appear at most three times. The largest total is therefore 213×3=639 meals, achievable by seeing every fortune exactly three times. At meal 640, the pigeonhole principle forces some type to have appeared at least four times. The question asks the largest possible avoiding total, not the next forcing total. **Answer: 639.**

For n>=3, \(\binom n3=n(n-1)(n-2)/6\) and \(P(n,2)=n(n-1)\). Equating and dividing by the nonzero n(n-1) gives (n-2)/6=1. Therefore n-2=6 and n=8. Check: choose(8,3)=56 and P(8,2)=8×7=56. **Answer: 8.**

Choose exponents a in {4,5,6} from the first factor and b in {3,4,5,6,7} from the second. The final geometric factor supplies exactly one term x^(10-a-b) whenever a+b<=10. For a=4 there are 4 possible b values (3–6); for a=5 there are 3 (3–5); for a=6 there are 2 (3–4). Each choice contributes coefficient 1. Total coefficient=4+3+2=9. **Answer: 9.**

Symmetric closure is R∪R inverse. Each of 120 directed edges can contribute at most one missing reverse, so the closure has at most 240 edges. This bound is attainable on 20 nodes: there are choose(20,2)=190 distinct unordered nonloop pairs, so select 120 of them and orient each only one way. All 120 reverses are then new. Loops or already-reversed pairs would reduce, not increase, the final edge count. **Answer: 240.**

A web graph represents each page by a vertex and each hyperlink from page u to page v by an edge u→v. In-degree counts edges entering v, so it measures pages linking to v in the usual simple web-graph model. It differs from outgoing links and from pages reachable through longer paths. **Answer: A.** A: **Correct:** Incoming links correspond to edges directed into v. B: **Incorrect:** Reachability includes paths and concerns outgoing access, not in-degree. C: **Incorrect:** Does not distinguish incoming from outgoing connections. D: **Incorrect:** URLs appearing on v correspond to its outgoing links, not its incoming links.

Using the source's convention that W27 has 27 total vertices, the wheel consists of an even cycle with 26 rim vertices and one hub. Alternate two colours around the even rim. The hub touches every rim vertex, so it requires a third colour. A triangle formed by the hub and two neighbouring rim vertices proves that fewer than three colours is impossible. Therefore the chromatic number is 3. Convention matters: texts defining Wn as a hub added to Cn would use W26 for this same wheel; their W27 has an odd rim and needs 4 colours. **Answer: 3.**

Under the source's edge-count height convention, a tree of height 31 can have a deepest root-to-node path containing 32 existing nodes. In the worst case, insertion compares with every node on such a search path before reaching a missing child link. Thus the maximum is height+1=32 key comparisons, assuming one three-way key comparison per visited node. A convention measuring height in nodes or separately counting pointer tests would use a different count. **Answer: 32.**

Read the expression as prefix notation: `* + * - 5 3 2 1 + 2 3`. Every binary operator consumes the next two expressions. First 5-3=2; then multiply by 2 to get 4; add 1 to get 5. The right-hand sum 2+3 is 5. Finally multiply these two results: 5×5=25. Parenthesised, the expression is (((5-3)×2)+1)×(2+3). **Answer: 25.**

A Hamiltonian path visits every vertex exactly once and uses an actual graph edge at every step. The sequence a,e,d,c,b,g,i,f,h,j has ten distinct vertices and the diagram contains all nine required edges: ae,ed,dc,cb,bg,gi,if,fh,hj. No closing edge from j back to a is required for a path. The Petersen graph lacks a Hamiltonian cycle, but that does not rule out Hamiltonian paths. **Answer: B.** A: **Incorrect:** Repeats f, so it is not a once-per-vertex path. B: **Correct:** Visits all ten vertices once using existing edges. C: **Incorrect:** Repeats g at the end. D: **Incorrect:** Uses nonexistent consecutive edges such as g-h in the shown graph. E: **Incorrect:** B explicitly provides a Hamiltonian path.

Every outer vertex is joined directly to its corresponding inner vertex. From an outer vertex, its two neighbouring outer vertices provide two inner vertices within two steps via their spokes. Its own inner neighbour is joined along the inner star to the remaining two inner vertices, also giving two-step routes. Thus every outer-inner distance is at most 2. Some pairs are not directly joined, so the maximum is exactly 2. **Answer: 2.**

Even integers are closed under addition: 2a+2b=2(a+b) is even. Integer addition is associative, so (x+y)+z=x+(y+z) holds within the set. A nonempty set with a closed associative binary operation is a semigroup. Identity and inverses are stronger properties and are not needed for this question. **Answer: A.** A: **Correct:** Closure and associativity both hold. B: **Incorrect:** There is no failure of either semigroup property.

Odd integers are closed under multiplication because \((2a+1)(2b+1)=2(2ab+a+b)+1\) is odd. Multiplication is associative, and 1 is an odd integer satisfying 1x=x1=x. Therefore the odd integers under multiplication form a monoid. Most odd integers do not have integer multiplicative inverses, but inverses are not required for a monoid. **Answer: A.** A: **Correct:** Closure, associativity and the identity 1 establish a monoid. B: **Incorrect:** Lack of inverses for values such as 3 does not prevent a monoid.

The even integers are closed under associative addition. Zero is even and is the additive identity. For every even integer 2k, its inverse -2k is also even and their sum is zero. Hence all group axioms hold, so (E,+) is a group; addition is also commutative, making it abelian. **Answer: A.** A: **Correct:** Every even integer has an even additive inverse, with identity zero. B: **Incorrect:** No group axiom fails for even integers under addition.