Discrete Structures for the ugc net and gate

Detailed Syllabus for Discrete Mathematics

1.         Proposition Logic:

Implication, Equivalence, Bidirectional, Converse, Inverse, Contra positive.
Rules of Inference (modus poners, modus tollens, hypothetical syllogism, disjunctive syllogism).
Precedence of logic operators.
Quantifiers, negation of quantifier, skolemization.
Horn clause, Definite clause, Goal clause.
Vacuous proof, Trivial Proof, Direct Proof, Indirect Proof.

Set, Relation, Function:

Real number, Integer, Positive Integer, Natural Number, Whole Number.
Set, null set, Equal Set, Euivalence set, Disjoint set, number of subset in a set.
Function, Domain, co- domain, Range, Types of function (Injective, Surjective, Bijective, One to One correspondence, Injective), Inverse of a function.
Cartesian product.
Relation and types of Relation.
Composition of functions.


Graph, self loop, parallel edge, simple graph, multi graph, pseudo graph, null graph, trivial graph, finite graph, isolated vertex, pendant vertex, connected graph, weakly connected graph, strongly connected graph.
Handshakking theorem.
Regular graph, complete graph, Bipartite graph, Havel hakimi theorem, complete bipartite graph.
Chromatic number of a graph, number of regions in a graph, predicate.
Isomorphism, elementary subdivision.
Adjacency matrix, vertex to edge connectivity.
Cut vertices, cut edges, vertex connectivity, number of articulation  points.
Euler circuit, Euler path, Hamiltonial circuit, Hamiltonian path, Dirac’s theorem, Oreo’s Theorem.
Clique, compliment of a graph.
Traversal: walk, path, Distance of vertex(u,v), eccentricity, Diameter, Radius.

Leave a Comment