Learn · Discrete Mathematics - IIITB
Lecture 46 of 72Week 8 Graph Theory Part I
Proof of Hall’s Marriage Theorem
Prof. Ashish Choudhury · IIIT Bangalore
Credits and licence
- From
- Discrete Mathematics - IIITB, IIIT Bangalore (at NPTEL)
- Licence
- CC BY-NC-SA, as NPTEL states it. Non-commercial use only.
- Attribution
- NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge. Coordinated by IISc Bangalore.
- Who can watch
- Tweens profiles and older. How courses are placed
All the lectures
- Introduction to Mathematical Logic
- Logical Equivalence
- SAT Problem
- Rules of Inference
- Resolution
- Tutorial 1: Part I
- Tutorial 1: Part II
- Predicate Logic
- Rules of Inferences in Predicate Logic
- Proof Strategies I
- Proof Strategies II
- Induction
- Tutorial 2: Part I
- Tutorial 2: Part II
- Sets
- Relations
- Operations on Relations
- Transitive Closure of Relations
- Warshall’s Algorithm for Computing Transitive Closure
- Tutorial 3
- Equivalence Relation
- Equivalence Relations and Partitions
- Partial Ordering
- Functions
- Tutorial 4: Part I
- Tutorial 4: Part II
- Countable and Uncountable Sets
- Examples of Countably Infinite Sets
- Cantor’s Diagonalization Argument
- Uncomputable Functions
- Tutorial 5
- Basic Rules of Counting
- Permutation and Combination
- Counting Using Recurrence Equations
- Solving Linear Homogeneous Recurrence Equations – Part I
- Solving Linear Homogeneous Recurrence Equations – Part II
- Tutorial 6: Part I
- Tutorial 6: Part II
- Solving Linear Non-Homogeneous Recurrence Equations
- Catalan Numbers
- Catalan Numbers – Derivation of Closed Form Formula
- Counting Using Principle of Inclusion-Exclusion
- Tutorial 7
- Graph Theory Basics
- Matching
- Proof of Hall’s Marriage Theorem
- Various Operations on Graphs
- Vertex and Edge Connectivity
- Tutorial 8
- Euler Path and Euler Circuit
- Hamiltonian Circuit
- Vertex and Edge Coloring
- Tutorial 9: Part I
- Tutorial 9: Part II
- Modular Arithmetic
- Prime Numbers and GCD
- Properties of GCD and Bézout’s Theorem
- Linear Congruence Equations and Chinese Remainder Theorem
- Uniqueness Proof of the CRT
- Fermat’s Little Theorem, Primality Testing and Carmichael Numbers
- Group Theory
- Cyclic Groups
- Subgroups
- Discrete Logarithm and Cryptographic Applications
- More Applications of Groups
- Rings, Fields and Polynomials
- Polynomials Over Fields and Properties
- Finite Fields and Properties I
- Finite Fields and Properties II
- Primitive Element of a Finite Field
- Applications of Finite Fields
- Goodbye and Farewell