Discrete Mathematics

Discrete Mathematics is the largest single contributor inside the 13-mark Engineering Mathematics block, and its reach extends far beyond that. Theory of Computation, Algorithms, Databases and Compiler Design all rest on the definitions established here, so a gap in this chapter is paid for repeatedly.

Every object in discrete mathematics is defined entirely by its axioms. A relation is transitive or it is not, according to a condition you can check mechanically. A structure is a group or it is not, according to four properties. Nothing depends on what the objects "really are".

That has an immediate consequence for how questions are answered. A claim is established by verifying the definition on every case, and refuted by exhibiting one counterexample. GATE questions are built almost entirely around the second half of that sentence, because a single well-chosen counterexample settles a statement that would otherwise need a proof.

So the working method is: state the definition precisely, then hunt for the smallest object that could break the claim. The empty set, the one-element set, the identity element and the two-vertex graph are where most counterexamples live.

1. Propositional Logic

A proposition is a statement with a definite truth value. Connectives combine propositions, and implication is the one that causes trouble.

Implication $p\to q$ is false only when $p$ is true and $q$ is false. In particular it is true whenever $p$ is false, regardless of $q$, which is the vacuous truth that most confuses candidates.

Three related forms must be kept distinct.

Only the contrapositive is equivalent to the original. The converse and inverse are equivalent to each other but not to the original, and this is examined directly.

Two identities carry most of the manipulation work.

$p\to q\equiv \neg p\vee q$

$\neg (p\wedge q)\equiv \neg p\vee \neg q$

The second is De Morgan's law, and its dual negates a disjunction into a conjunction.

A formula is a tautology if it is true under every assignment, a contradiction if false under every one, and satisfiable if true under at least one. These three are what questions actually ask about, and the fastest route is usually to assume the formula is false and derive a contradiction.

For a formula with $n$ variables the truth table has $2^n$ rows, so building it is only practical up to about three variables. Beyond that, the assume-false method or algebraic simplification is required.

2. Predicate Logic and Quantifiers

Predicate logic adds quantifiers over a domain, and the order of unlike quantifiers changes the meaning.

$\forall x\exists yP(x,y)$ says every $x$ has some $y$, possibly a different one each time. $\exists y\forall xP(x,y)$ says one single $y$ works for every $x$. The second implies the first; the first does not imply the second.

Negation moves inward by flipping each quantifier and negating the body:

$\neg \forall xP(x)\equiv \exists x\neg P(x)$

A universally quantified statement over an empty domain is vacuously true, which is the source of many counterexamples. "All elements of the empty set are prime" is true.

Like quantifiers commute freely — two consecutive $\forall$ can be swapped, as can two consecutive $\exists$ — but unlike quantifiers never can.

3. Sets, Relations and Functions

For a set $A$ with $n$ elements, the power set has $2^n$ elements, and the number of relations on $A$ is $2^{n^2}$, since a relation is any subset of $A\times A$.

A relation on $A$ can hold five properties, and each is a mechanical check.

Antisymmetric is not the negation of symmetric. A relation can be both, as the identity relation is, and it can be neither.

An equivalence relation is reflexive, symmetric and transitive, and it partitions the set into disjoint equivalence classes. The correspondence runs both ways: every partition induces an equivalence relation and vice versa, so counting equivalence relations on an $n$-set is counting its partitions, which is the Bell number $B_n$.

For functions $f:A\to B$ with $|A|=m$ and $|B|=n$:

• Total functions: $n^m$
• Injective functions: $n(n-1)\cdots (n-m+1)$, requiring $m\le n$
• Surjective functions: by inclusion-exclusion, and zero unless $m\ge n$
• Bijections: $n!$ when $m=n$, and none otherwise

A function on a finite set is injective if and only if it is surjective. This fails on infinite sets, where the successor function on the natural numbers is injective but not surjective — a standard source of counterexamples.

4. Partial Orders and Lattices

A partial order is reflexive, antisymmetric and transitive. The pair of a set with such a relation is a poset, and a Hasse diagram draws it with reflexive and transitive edges omitted and direction implied upward.

Two elements are comparable if one is related to the other. In a total order every pair is comparable; in a general poset some pairs are not, and those incomparable pairs are what most questions turn on.

The least upper bound of two elements is their join, written $a\vee b$, and the greatest lower bound is their meet, $a\wedge b$.

A lattice is a poset in which every pair of elements has both a meet and a join. A poset with a missing join anywhere is not a lattice, and finding that one pair is how such questions are answered.

Every finite lattice has a greatest and a least element. A lattice is distributive if meet distributes over join and vice versa, and it is complemented if every element has a complement relative to the bounds. A Boolean algebra is a complemented distributive lattice.

The divisibility relation on the divisors of $n$ is a lattice in which meet is the greatest common divisor and join is the least common multiple, and it is the standard example questions are built from.

5. Groups and Algebraic Structures

Structures are distinguished by which axioms they satisfy, and the hierarchy is cumulative.

Closure must be checked first and is where most examples fail. The set of odd integers under addition is not closed, so it is not even a semigroup.

In a group, the identity is unique and each element has a unique inverse. The cancellation laws hold in any group, so $ax=ay$ implies $x=y$, and this is often all a question needs.

Lagrange's theorem states that the order of a subgroup divides the order of the group. The immediate consequence is that a group of prime order has no proper subgroups and must be cyclic, which answers a whole family of questions in one step.

The order of an element is the smallest positive $k$ with $a^k=e$, and by Lagrange it divides the group's order.

6. Counting and the Pigeonhole Principle

Beyond the standard permutation and combination counts, three techniques carry most GATE questions.

Inclusion-exclusion corrects for over-counting overlaps:

$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|A\cap C|+|A\cap B\cap C|$

The alternating pattern continues for more sets, and the term for $k$ sets carries sign $(-1{)}^{k+1}$.

Distributing $r$ identical objects into $n$ distinct boxes is the stars-and-bars count $\left(\genfrac{}{}{0ex}{}{r+n-1}{n-1}\right)$, and requiring each box to be non-empty gives $\left(\genfrac{}{}{0ex}{}{r-1}{n-1}\right)$.

The pigeonhole principle states that placing $n$ objects into $k$ boxes with $n>k$ forces some box to hold at least two. The generalised form guarantees a box with at least $\lceil n/k\rceil$ objects.

The difficulty in pigeonhole questions is never the principle; it is choosing what the boxes are. The boxes are almost always defined by a remainder, a range, or a pair-sum, and once named the question collapses.

7. Recurrence Relations

A linear homogeneous recurrence with constant coefficients is solved through its characteristic equation.

For $a_n=c_1{a}_{n-1}+c_2{a}_{n-2}$, write $r^2=c_{1}r+c_2$ and solve for the roots.

With distinct roots $r_1$ and $r_2$, the solution is $a_n=A{r}_1^n+B{r}_2^n$, with $A$ and $B$ fixed by the initial conditions.

With a repeated root $r$, the solution is $a_n=(A+Bn)r^n$. The extra factor of $n$ is required because two independent solutions are needed and $r^n$ alone supplies only one.

For a non-homogeneous recurrence, the general solution is the homogeneous solution plus a particular solution matching the form of the driving term.

Generating functions convert a recurrence into an algebraic equation. Multiplying each term by $x^n$ and summing gives a closed form in $x$, from which the coefficient of $x^n$ is recovered by partial fractions. Two expansions cover almost every case:

$\frac{1}{1-x}={\sum }_{n\ge 0}{x}^n\frac{1}{(1-x{)}^2}={\sum }_{n\ge 0}(n+1)x^n$

8. Graph Theory

A graph is a set of vertices with a set of edges. The single most useful fact is the handshaking lemma.

${\sum }_v\mathrm{deg}(v)=2|E|$

The sum of degrees is twice the number of edges, from which it follows immediately that the number of odd-degree vertices is even.

Several standard results are examined directly.

A simple graph on $n$ vertices has at most $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ edges. A tree on $n$ vertices has exactly $n-1$ edges, is connected, and is acyclic — and any two of those three properties imply the third.

A graph has an Euler circuit if and only if it is connected and every vertex has even degree, and an Euler path if exactly two vertices have odd degree. The condition is checkable in one pass.

Hamiltonian circuits have no such characterisation, which is precisely why the problem is hard. Dirac's condition — every vertex of degree at least $n/2$ in a graph on $n\ge 3$ vertices — is sufficient but not necessary.

A graph is bipartite if and only if it contains no odd cycle, which is equivalent to being 2-colourable. This equivalence answers most colouring questions about bipartite graphs in one line.

The chromatic number of a complete graph $K_n$ is $n$, of any cycle of even length is 2, and of any cycle of odd length is 3.

A planar graph satisfies Euler's formula relating vertices, edges and faces:

$V-E+F=2$

for a connected planar graph. From it follows $E\le 3V-6$ for a simple planar graph with $V\ge 3$, and $E\le 2V-4$ if the graph is additionally triangle-free.

Applying these bounds shows immediately that $K_5$ and $K_{3,3}$ are non-planar, and Kuratowski's theorem states that these two are the only obstructions up to subdivision.

The number of labelled trees on $n$ vertices is $n^{n-2}$, by Cayley's formula, which appears regularly as a direct question.

9. Worked Examples

Example 1. How many binary relations on a set of 3 elements are both reflexive and symmetric?

A relation is a subset of $A\times A$, which has 9 pairs for $|A|=3$.

Reflexivity forces the 3 diagonal pairs to be present, so they are not free choices.

The remaining 6 off-diagonal pairs come in 3 symmetric couples: $(a,b)$ with $(b,a)$, and similarly for the other two pairs of distinct elements. Symmetry forces each couple to be included or excluded together, so each couple is one free binary choice.

The count is therefore $2^3=8$.

The general formula follows by the same reasoning: for an $n$-set, the number of reflexive symmetric relations is $2^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$.

Example 2. Consider the poset of divisors of 30 under divisibility. Is it a lattice, and what is its greatest element?

The divisors are 1, 2, 3, 5, 6, 10, 15, 30.

Under divisibility, the meet of two elements is their greatest common divisor and the join is their least common multiple. Both always exist within this set, because any gcd or lcm of two divisors of 30 is itself a divisor of 30.

So every pair has a meet and a join, and the poset is a lattice.

The greatest element is 30, since every divisor divides it, and the least is 1.

It is worth noting why this works: 30 is a product of distinct primes, so its divisor lattice is isomorphic to the power set of a 3-element set under inclusion, and is therefore a Boolean algebra. Had the number been 12, with a repeated prime factor, the lattice would not be complemented.

Example 3. Is $(p\to q)\to (\neg p\to \neg q)$ a tautology?

Assume it is false. An implication is false only when the antecedent is true and the consequent false.

So $p\to q$ is true and $\neg p\to \neg q$ is false.

For $\neg p\to \neg q$ to be false, $\neg p$ must be true and $\neg q$ false, giving $p$ false and $q$ true.

Check these against the antecedent: with $p$ false, $p\to q$ is vacuously true, which is consistent.

We have found a satisfying assignment for the negation, so the formula is not a tautology. The counterexample is $p$ false, $q$ true.

This also confirms that the inverse of an implication is not equivalent to it, which is exactly what the formula was testing.

Example 4. In a group $G$ of order 15, how many elements of order 3 can there be?

By Lagrange's theorem, the order of any element divides 15, so element orders can only be 1, 3, 5 or 15.

Elements of order 3 generate cyclic subgroups of order 3. Each such subgroup contains the identity plus two elements of order 3.

Two distinct subgroups of prime order intersect only in the identity, since their intersection is a subgroup of both and its order must divide 3, forcing it to be 1 or 3, and 3 would make them equal.

So elements of order 3 come in disjoint pairs, one pair per subgroup of order 3, and the answer must be even.

In fact, by Sylow theory the number of subgroups of order 3 in a group of order 15 is exactly 1, giving exactly 2 elements of order 3. The point worth carrying forward is that Lagrange alone already restricts the answer to an even number, which is usually enough to eliminate options.

Example 5. Solve $a_n=5a_{n-1}-6a_{n-2}$ with $a_0=1$ and $a_1=4$.

Write the characteristic equation: $r^2=5r-6$, that is, $r^2-5r+6=0$.

Factoring gives $(r-2)(r-3)=0$, so the roots are 2 and 3, which are distinct.

The general solution is $a_n=A\cdot 2^n+B\cdot 3^n$.

Apply the initial conditions. From $a_0=1$: $A+B=1$. From $a_1=4$: $2A+3B=4$.

Subtracting twice the first equation from the second gives $B=2$, and then $A=-1$.

So $a_n=-2^n+2\cdot 3^n$.

Verify at $n=2$: the recurrence gives $5(4)-6(1)=14$, and the formula gives $-4+18=14$. The check takes seconds and catches sign errors, which are the commonest failure in this topic.

Example 6. A simple connected planar graph has 10 vertices, each of degree 3. How many faces does it have?

By the handshaking lemma, the sum of degrees is twice the number of edges.

${\sum }_v\mathrm{deg}(v)=10\times 3=30=2|E|$

So $|E|=15$.

Check planarity is even possible: $E\le 3V-6$ gives $15\le 24$, which holds, so the constraint is not violated.

Apply Euler's formula for a connected planar graph:

$V-E+F=2⟹10-15+F=2⟹F=7$

The graph has 7 faces, counting the unbounded outer face.

This graph is in fact the Petersen graph's planar cousin; the Petersen graph itself is 3-regular on 10 vertices but is famously non-planar, which is a reminder that satisfying $E\le 3V-6$ is necessary and not sufficient for planarity.

Summary

Every object here is defined by its axioms, so verify a claim by checking the definition and refute it with one counterexample, usually built from the empty set, a one-element set, or a two-vertex graph.

Implication is false only when the antecedent is true and the consequent false. Only the contrapositive is equivalent to the original; the converse and inverse are not.

Unlike quantifiers do not commute: one $y$ for all $x$ is strictly stronger than an $x$-dependent $y$.

Antisymmetric is not the negation of symmetric. An equivalence relation partitions its set, and the partitions correspond exactly to the equivalence relations.

A lattice needs both a meet and a join for every pair; a single missing join disqualifies it. Divisors under divisibility give a lattice with gcd as meet and lcm as join.

Check closure first when testing an algebraic structure. Lagrange's theorem forces subgroup and element orders to divide the group order, and a group of prime order must be cyclic.

Inclusion-exclusion alternates signs; stars and bars counts identical objects into distinct boxes; and the difficulty in a pigeonhole question is always naming the boxes.

Solve linear recurrences through the characteristic equation, remembering the extra factor of $n$ for a repeated root.

The degree sum is twice the edge count, so odd-degree vertices are even in number. Euler circuits need all degrees even; bipartite is equivalent to having no odd cycle; and $V-E+F=2$ with $E\le 3V-6$ bounds planar graphs.