All Discrete Mathematics questions

Single correct

• A512
• B1025
• C1023
• D255

One or more correct

• AThe degree of $v$ is at least $k + 1$
• BThe vertex $v$ is on a path of length $k + 1$
• CThe vertex $v$ is on a cycle of length $k + 1$
• DThe vertex $v$ is a part of a clique of size $k$

One or more correct

• AIf $G$ is 2-colorable, then $G$ may contain cycles of odd length
• BIf $G$ is 2-colorable, then $G$ may contain cycles of even length
• CAn optimal algorithm for testing whether $G$ is 2-colorable runs in time $\Theta(|V| + |E|)$, if $G$ is represented as an adjacency list
• DAn optimal algorithm for testing whether $G$ is 2-colorable runs in time $\Theta(|E| \log |V|)$, if $G$ is represented as an adjacency list

Numerical answer

Single correct

• A$(\exists y)(\forall x)\,((x \ne y) \to (M(x, y) \wedge \neg M(y, x)))$
• B$(\forall y)(\exists x)\,((x \ne y) \to (M(x, y) \wedge \neg M(y, x)))$
• C$(\exists y)(\exists x)\,((x \ne y) \to (M(x, y) \wedge \neg M(y, x)))$
• D$(\forall y)(\forall x)\,((x \ne y) \to (M(x, y) \wedge \neg M(y, x)))$

One or more correct

• AReflexive
• BSymmetric
• CTransitive
• DAntisymmetric

Single correct

• A$\dfrac{1}{n}$
• B$\dfrac{1}{2n-3}$
• C0
• D$\dfrac{1}{n-1}$

Single correct

• A$g(.)$ must be an onto (surjective) function.
• B$g(.)$ must be a one-to-one (injective) function.
• C$g(.)$ must be a bijective function, that is, both one-to-one and onto.
• D$g(.)$ is not required to be a one-to-one or onto function.

Numerical answer

One or more correct

• A$\forall x \exists y \exists z\, (mother(y, x) \wedge \neg mother(z, x))$
• B$\forall x \exists y\, [mother(y, x) \wedge \forall z\, (noteq(z, y) \to \neg mother(z, x))]$
• C$\forall x \forall y\, [mother(y, x) \to \exists z\, (mother(z, x) \wedge \neg noteq(z, y))]$
• D$\forall x \exists y\, [mother(y, x) \wedge \neg \exists z\, (noteq(z, y) \wedge mother(z, x))]$

One or more correct

• A$(\text{F}, \odot)$ is an Abelian group.
• B$(\text{F}, \odot)$ is an Abelian monoid.
• C$(\text{F}, \odot)$ is a non-Abelian group.
• D$(\text{F}, \odot)$ is a non-Abelian monoid.

Single correct

• A$(P(0) \wedge (\forall x\, [P(x) \Rightarrow P(x+1)])) \Rightarrow (\forall x\, P(x))$
• B$(P(0) \wedge (\forall x\, [P(x) \Rightarrow P(x-1)])) \Rightarrow (\forall x\, P(x))$
• C$(P(1000) \wedge (\forall x\, [P(x) \Rightarrow P(x-1)])) \Rightarrow (\forall x\, P(x))$
• D$(P(1000) \wedge (\forall x\, [P(x) \Rightarrow P(x+1)])) \Rightarrow (\forall x\, P(x))$

One or more correct

• A$\preccurlyeq$ is a symmetric relation
• B$(\mathcal{F}, \preccurlyeq)$ is a partial order
• C$(\mathcal{F}, \preccurlyeq)$ is a lattice
• D$\preccurlyeq$ is an equivalence relation

Numerical answer

Numerical answer

One or more correct

• A$G$ contains a complete subgraph with $k$ vertices
• B$G$ contains an independent set of size at least $n/k$
• C$G$ contains at least $k(k - 1)/2$ edges
• D$G$ contains a vertex of degree at least $k$

One or more correct

• AOperator $\lozenge$ obeys the associative law
• BOperator $\square$ obeys the associative law
• COperator $\lozenge$ over the operator $\square$ obeys the distributive law
• DOperator $\square$ over the operator $\lozenge$ obeys the distributive law

Single correct

• A$q \to \neg p$
• B$q \to p$
• C$p \to q$
• D$\neg p \to q$

Single correct

• A$G$ is a cycle
• B$G$ is a perfect matching
• C$G$ is a complete graph
• DThere is no such graph $G$

Numerical answer