# Fundamentals of Discrete Mathematics (MA 5350)

## Instructor: Narayanan N

Lecture Schedule: 9:00am to 9:50am Monday
8:00am - 8:50am Tuesday
12:00noon - 12:50pm Wednesday
Venue: CRC 103

### Lecture 15

Other proof techniques: Contraposition, Contradiction, biconditional and uniqueness.

### Lecture 14

Review of PHP and Erdos-Szekers theorem on subsequences. Dirichlet theorem.

### Lecture 13

Proof techniques. What is expected from a mathematics proof. Logical arguments in the background. Direct proof. Second assignment due on 16th Sept.

### Lecture 12

Predicate logic and quantifiers. The universal $\forall$ and existential $\exists$ quantifiers. Free variables.

Class test 1

### Lecture 10

More logical puzzles. Formalising the problems to analyse them. Predicates.

### Lecture 9

Propositional logic. Truth tables, truth function. Modus ponens and other Tautological formulae. Prisoners and the 5 hats problem.

### Lecture 8

Sentencial logic and advantage of symbolism, the five logical connectives. Practical examples/

### Lecture 7

What is logic? Logic in language.

### Lecture 6

Bipratite characterization, The Peterson graph, some example problems.

### Lecture 5

Maximum degree $\Delta(G)$ and minimum degree $\delta(G)$. Some theorems on walks, paths and cycles.

### Lecture 4

Independent sets and cliques, isomorphism, adjacency and incident matrices, connected components.

### Lecture 3

Walks, Paths, Cycle, Job assignment and Bipartite graphs, Scheduling and Colouring, Map colouring.

#### Homework:

Problems from Sectiosn 1.1 and 1.2 of D.B. West.

### Lecture 2

Graph Theory: Graphs, subgraphs, adjacency, degree, first theorem of graph theory.

### Lecture 1

Introduction to the course; Pictorial representation of graphs. Pigeonhole principle.

#### Homework:

How to communicate Mathematics: Read this.