### 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.

Duality.

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.

Probability.

### Graph:

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.