BSc CSIT (TU) Science Discrete Structure (BSc CSIT, CSC160) Question Paper 2080 Nepal

Proof Techniques

1. Direct Proof

To prove a statement $p \Rightarrow q$, we assume $p$ is true and, through a sequence of valid logical steps, deduce that $q$ is true.

Example: If $n$ is an even integer, then $n^2$ is even.

Assume $n$ is even, so $n = 2k$ for some integer $k$. Then $n^2 = (2k)^2 = 4k^2 = 2(2k^2)$, which is $2 \times (\text{integer})$, hence even. $\blacksquare$

2. Proof by Contraposition

To prove $p \Rightarrow q$, we instead prove its logically equivalent contrapositive $\lnot q \Rightarrow \lnot p$.

Example: If $n^2$ is even, then $n$ is even.

Contrapositive: If $n$ is odd, then $n^2$ is odd. Let $n = 2k+1$. Then $n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$, which is odd. Hence the original statement holds. $\blacksquare$

3. Proof by Contradiction

To prove a statement $p$, we assume $\lnot p$ is true and derive a contradiction (something always false). Since the assumption leads to absurdity, $p$ must be true.

Example: There is no largest integer.

Assume there is a largest integer $N$. Then $N+1$ is also an integer and $N+1 > N$, contradicting that $N$ is largest. Hence no largest integer exists. $\blacksquare$

Proof that $\sqrt{2}$ is Irrational (by Contradiction)

Assume, for contradiction, that $\sqrt{2}$ is rational. Then we can write

where $p, q$ are integers, $q \neq 0$, and the fraction is in lowest terms (i.e. $p$ and $q$ have no common factor; $\gcd(p,q)=1$).

Squaring both sides:

Thus $p^2$ is even, which forces $p$ to be even (since the square of an odd number is odd). Write $p = 2m$. Then

so $q^2$ is even, hence $q$ is even.

But now both $p$ and $q$ are even, so they share the common factor $2$ — contradicting our assumption that $\gcd(p,q)=1$.

This contradiction shows our assumption was false. Therefore $\sqrt{2}$ is irrational. $\blacksquare$

Group, Ring and Field

Group

A non-empty set $G$ with a binary operation $*$ is a group $(G, *)$ if it satisfies:

1. Closure: $a * b \in G$ for all $a, b \in G$.
2. Associativity: $(a*b)*c = a*(b*c)$.
3. Identity: there exists $e \in G$ such that $a * e = e * a = a$.
4. Inverse: for each $a \in G$ there exists $a^{-1} \in G$ with $a * a^{-1} = a^{-1} * a = e$.

If additionally $a*b = b*a$, the group is abelian (commutative).

Example: $(\mathbb{Z}, +)$, the integers under addition.

Ring

A set $R$ with two operations $+$ (addition) and $\cdot$ (multiplication) is a ring $(R, +, \cdot)$ if:

1. $(R, +)$ is an abelian group.
2. Multiplication is associative.
3. Multiplication distributes over addition: $a(b+c) = ab + ac$ and $(a+b)c = ac + bc$.

Example: $(\mathbb{Z}, +, \cdot)$, the integers under usual addition and multiplication.

Field

A field is a commutative ring $(F, +, \cdot)$ with a multiplicative identity $1 \neq 0$ in which every non-zero element has a multiplicative inverse. That is, $(F, +)$ is an abelian group and $(F \setminus \{0\}, \cdot)$ is an abelian group.

Example: $(\mathbb{R}, +, \cdot)$, the real numbers; also $(\mathbb{Q}, +, \cdot)$.

Integers under Addition Form a Group

Let $G = \mathbb{Z}$ and the operation be ordinary addition $+$. We verify the group axioms:

(i) Closure: For any $a, b \in \mathbb{Z}$, $a + b$ is an integer, so $a + b \in \mathbb{Z}$. ✓

(ii) Associativity: For all $a, b, c \in \mathbb{Z}$, $(a + b) + c = a + (b + c)$ (a known property of integer addition). ✓

(iii) Identity: $0 \in \mathbb{Z}$ and for every $a$, $a + 0 = 0 + a = a$. So $0$ is the additive identity. ✓

(iv) Inverse: For each $a \in \mathbb{Z}$, its inverse is $-a \in \mathbb{Z}$, since $a + (-a) = (-a) + a = 0$. ✓

All four axioms hold, so $(\mathbb{Z}, +)$ is a group. Moreover $a + b = b + a$, so it is an abelian group. $\blacksquare$

Graph Coloring

A (proper vertex) coloring of a graph $G = (V, E)$ is an assignment of colors to the vertices such that no two adjacent vertices receive the same color. A coloring that uses at most $k$ colors is called a k-coloring, and $G$ is then said to be k-colorable.

Chromatic Number

The chromatic number $\chi(G)$ of a graph $G$ is the smallest number of colors needed to properly color $G$.

For example, a graph with no edges has $\chi = 1$; a bipartite graph with at least one edge has $\chi = 2$.

Four Color Theorem

Statement: Every planar graph (a graph that can be drawn in the plane with no edges crossing) is 4-colorable; equivalently, any map drawn on a plane can be colored using at most four colors so that no two adjacent regions share a color. Thus for any planar graph $G$, $\chi(G) \le 4$.

Chromatic Number of $K_n$ (Complete Graph)

In $K_n$ every vertex is adjacent to every other vertex, so all $n$ vertices are pairwise adjacent and each must get a distinct color.

Chromatic Number of $C_n$ (Cycle)

For a cycle on $n$ vertices:

• If $n$ is even, the vertices can be alternately 2-colored, so $\chi(C_n) = 2$.
• If $n$ is odd, two colors cannot alternate around the odd cycle (the last vertex clashes with the first), so a third color is needed: $\chi(C_n) = 3$.

Logical Implication (Conditional, $p \rightarrow q$): The compound proposition "if $p$ then $q$", which is false only when $p$ is true and $q$ is false, and true in all other cases. Here $p$ is the hypothesis and $q$ the conclusion.

Biconditional ($p \leftrightarrow q$): The proposition "$p$ if and only if $q$", which is true exactly when $p$ and $q$ have the same truth value (both true or both false). It is equivalent to $(p \rightarrow q) \wedge (q \rightarrow p)$.

A function $f: \mathbb{R} \to \mathbb{R}$ is one-to-one (injective) if $f(a) = f(b)$ implies $a = b$ for all $a, b$ in the domain. Equivalently, distinct inputs must give distinct outputs.

To show $f(x) = x^2$ is not one-to-one, we exhibit a counterexample — two different inputs with the same output.

Take $a = 2$ and $b = -2$. Then

So $f(2) = f(-2) = 4$ but $2 \neq -2$.

More generally, for every $x \neq 0$, $f(x) = f(-x) = x^2$ while $x \neq -x$. Since distinct inputs produce equal outputs, $f$ violates the injectivity condition.

Therefore $f(x) = x^2$ from $\mathbb{R}$ to $\mathbb{R}$ is not one-to-one. $\blacksquare$

Cartesian Product: For two sets $A$ and $B$, the Cartesian product $A \times B$ is the set of all ordered pairs $(a, b)$ where the first element $a$ comes from $A$ and the second element $b$ comes from $B$:

If $A$ has $m$ elements and $B$ has $n$ elements, then $|A \times B| = m \cdot n$. Note that in general $A \times B \neq B \times A$ (order matters in the pairs).

Example: Let $A = \{1, 2\}$ and $B = \{x, y\}$. Then

which has $2 \times 2 = 4$ ordered pairs.

We prove $2^n > n$ for all integers $n \ge 1$ by mathematical induction.

Basis Step ($n = 1$):

So the statement holds for $n = 1$. ✓

Inductive Hypothesis: Assume the statement is true for some integer $k \ge 1$, i.e.

Inductive Step: We must show $2^{k+1} > k+1$.

Now $2k = k + k \ge k + 1$ because $k \ge 1$. Therefore

The statement holds for $k+1$.

Conclusion: By the principle of mathematical induction, $2^n > n$ for all integers $n \ge 1$. $\blacksquare$

Directed Graph (Digraph): A graph $G = (V, E)$ in which each edge has a direction — it is an ordered pair $(u, v)$ representing an arrow from $u$ (tail) to $v$ (head). The edge $(u, v)$ is different from $(v, u)$.

Example: $V = \{A, B, C\}$, $E = \{(A, B), (B, C), (A, C)\}$. Here there is an arrow from $A$ to $B$ but not necessarily from $B$ to $A$. Such graphs model one-way streets, web links, or task dependencies.

Undirected Graph: A graph $G = (V, E)$ in which edges have no direction — each edge is an unordered pair $\{u, v\}$, so $\{u, v\}$ and $\{v, u\}$ denote the same edge (the connection is symmetric).

Example: $V = \{A, B, C\}$, $E = \{\{A, B\}, \{B, C\}, \{A, C\}\}$ — a triangle. This models mutual relationships such as friendships or two-way roads.

Key difference: In a digraph we speak of in-degree and out-degree of a vertex; in an undirected graph each vertex has a single degree (number of incident edges).

Minimum Spanning Tree (MST): Given a connected, weighted, undirected graph $G = (V, E)$, a spanning tree is a subgraph that is a tree and includes every vertex of $G$ (so it has $|V|$ vertices and $|V| - 1$ edges, and is connected with no cycles). A minimum spanning tree is a spanning tree whose total edge weight is as small as possible among all spanning trees of $G$.

Two algorithms to find an MST:

1. Kruskal's algorithm — repeatedly add the smallest-weight edge that does not form a cycle (uses a disjoint-set / union-find structure).
2. Prim's algorithm — grow the tree from a starting vertex by repeatedly adding the cheapest edge that connects a vertex inside the tree to one outside it.

(Borůvka's algorithm is another valid example.) Both Kruskal's and Prim's are greedy algorithms that produce a minimum spanning tree.

Semigroup: An algebraic structure $(S, *)$ consisting of a non-empty set $S$ with a binary operation $*$ that satisfies:

1. Closure: $a * b \in S$ for all $a, b \in S$.
2. Associativity: $(a * b) * c = a * (b * c)$ for all $a, b, c \in S$.

Example: $(\mathbb{N}, +)$, the set of natural numbers under addition — closed and associative (but $\mathbb{N}$ here without 0 has no identity).

Monoid: A semigroup that additionally contains an identity element. So $(M, *)$ is a monoid if:

1. Closure holds.
2. Associativity holds.
3. Identity: there exists $e \in M$ such that $a * e = e * a = a$ for all $a \in M$.

Example: $(\mathbb{N}_0, +)$ where $\mathbb{N}_0 = \{0, 1, 2, \dots\}$, under addition, with identity $0$. Another example is the set of strings over an alphabet under concatenation, with the empty string as identity.

Relationship: Every monoid is a semigroup, but a semigroup is a monoid only if it has an identity element.

We solve $7x \equiv 1 \pmod{26}$, i.e. find the multiplicative inverse of $7$ modulo $26$.

Since $\gcd(7, 26) = 1$, the inverse exists and is unique modulo $26$. Use the Extended Euclidean Algorithm.

Euclidean algorithm:

Back-substitution:

So $-11 \cdot 7 \equiv 1 \pmod{26}$, giving $x \equiv -11 \pmod{26}$.

Reduce to a positive residue: $-11 + 26 = 15$.

Check: $7 \times 15 = 105 = 4 \times 26 + 1 = 104 + 1$, so $105 \equiv 1 \pmod{26}$. ✓

Thus the multiplicative inverse of $7$ modulo $26$ is $15$.

Binomial Theorem

For any real numbers $x, y$ and non-negative integer $n$:

where $\binom{n}{k} = \dfrac{n!}{k!\,(n-k)!}$ is the binomial coefficient. The coefficients correspond to row $n$ of Pascal's triangle.

Expansion of $(x + y)^4$

Here $n = 4$, and the coefficients $\binom{4}{k}$ for $k = 0,1,2,3,4$ are $1, 4, 6, 4, 1$.