# Introduction to Algebraic Graph Theory - Institution: IIT Indore - Department: Computer Science and Engineering - Teacher: Prof. Ranveer Singh - Level: Undergraduate - Language: English - Subjects: Computer science, Engineering - Source: [NPTEL](https://nptel.ac.in/courses/106106698) - Licence: [CC BY-NC-SA](https://nptel.ac.in/faq) (Non-commercial use only.) - Syllabus: [at the source](https://nptel.ac.in/courses/106106698) - Who can watch: Tweens profiles and older (sources give no ratings; placed by Invisible Network from the source's own words) ## Lectures 1. [Warm-up with graphs](https://invisiblenetwork.ai/learn/nptel/106106698/a49f03306d8a) (Video) 2. [Incidence matrix, cofactors of the Laplacian matrix (towards Matrix-Tree Theorem)](https://invisiblenetwork.ai/learn/nptel/106106698/56a48cb62b6f) (Video) 3. [Determinant of submatrices of incidence matrices and characterization of spanning trees](https://invisiblenetwork.ai/learn/nptel/106106698/aebc82a9b92e) (Video) 4. [Cauchy-Binet theorem and the proof of matrix-tree theorem](https://invisiblenetwork.ai/learn/nptel/106106698/cb3c46f3caa0) (Video) 5. [Rank of incidence matrix and the number of connected components](https://invisiblenetwork.ai/learn/nptel/106106698/58d79bd3e1ae) (Video) 6. [Rank and acyclic graphs, 0-1 incidence matrix and characterization of bipartite graph](https://invisiblenetwork.ai/learn/nptel/106106698/289b5a36305e) (Video) 7. [Introduction of the eigenvalues and eigenvector](https://invisiblenetwork.ai/learn/nptel/106106698/094ad3c642e6) (Video) 8. [Adjacency matrix and number of walks; powers of a symmetric matrix](https://invisiblenetwork.ai/learn/nptel/106106698/cc7df224e0d5) (Video) 9. [The spectral theorem](https://invisiblenetwork.ai/learn/nptel/106106698/2392d7ce08e1) (Video) 10. [Rayleigh quotient and the eigenvalues](https://invisiblenetwork.ai/learn/nptel/106106698/f7b81868a12d) (Video) 11. [A bound on the diameter of a graph using the number of distinct eigenvalues](https://invisiblenetwork.ai/learn/nptel/106106698/edc5b3bb7dd8) (Video) 12. [The rank of a symmetric matrix equals the number of nonzero eigenvalues.](https://invisiblenetwork.ai/learn/nptel/106106698/22f70342da58) (Video) 13. [Perron-Frobenius theorem for nonnegative symmetric matrices](https://invisiblenetwork.ai/learn/nptel/106106698/a06435c0fdd2) (Video) 14. [The consequences of the Perron-Frobenius theorem (the properties of the largest eigenvalue and the corresponding eigenvectors)](https://invisiblenetwork.ai/learn/nptel/106106698/a7c1f7496248) (Video) 15. [Eigenvalues of a graph and its subgraph; a relation between the largest eigenvalue and the degree(s)](https://invisiblenetwork.ai/learn/nptel/106106698/782be1feeb7f) (Video) 16. [Cauchy interlace theorem](https://invisiblenetwork.ai/learn/nptel/106106698/4526bb470e90) (Video) 17. [Bipartite graphs and their eigenvalues](https://invisiblenetwork.ai/learn/nptel/106106698/90cc5f4f0876) (Video) 18. [Positive semi-definite matrices and the eigenvalues of their partitioned form](https://invisiblenetwork.ai/learn/nptel/106106698/a660b58c86b1) (Video) 19. [The eigenvalues of a symmetric matrix in partitioned form](https://invisiblenetwork.ai/learn/nptel/106106698/ee6336445da9) (Video) 20. [Bounds on chromatic number, clique number, and independence number](https://invisiblenetwork.ai/learn/nptel/106106698/4f6be2546fa8) (Video) 21. [Introduction to lazy random walk, walk matrix](https://invisiblenetwork.ai/learn/nptel/106106698/cf966b5a7803) (Video) 22. [Convergence of lazy random walk](https://invisiblenetwork.ai/learn/nptel/106106698/0cee3992643f) (Video) 23. [Rate of convergence of lazy random walk](https://invisiblenetwork.ai/learn/nptel/106106698/5fdc5888ac0a) (Video) 24. [Regular graphs, spectral properties, bound on size of independent set](https://invisiblenetwork.ai/learn/nptel/106106698/565c0e781861) (Video) 25. [Strongly regular graphs, their eigenvalues, and characterization](https://invisiblenetwork.ai/learn/nptel/106106698/54ef8ab0a959) (Video) 26. [The friendship theorem](https://invisiblenetwork.ai/learn/nptel/106106698/6b1d5c86e447) (Video) 27. [Introduction to cospectral graphs](https://invisiblenetwork.ai/learn/nptel/106106698/e8826f791c6f) (Video) 28. [Godsil McKay switching to generate cospectral graphs](https://invisiblenetwork.ai/learn/nptel/106106698/9cef94bd7b42) (Video) 29. [Cartesian product and their eigenvalues, Shrikhande graph](https://invisiblenetwork.ai/learn/nptel/106106698/e4168952349d) (Video) 30. [Graph determined by the spectrum](https://invisiblenetwork.ai/learn/nptel/106106698/507c4b88bf1f) (Video) 31. [Sensitivity, block sensitivity and hypercube graph](https://invisiblenetwork.ai/learn/nptel/106106698/db2c846a534d) (Video) 32. [Proof of sensitivity conjecture](https://invisiblenetwork.ai/learn/nptel/106106698/8700f0c51540) (Video) 33. [Introduction to expander graphs](https://invisiblenetwork.ai/learn/nptel/106106698/fd59977f940a) (Video) 34. [A lower bound on Cheeger constant, and expander mixing lemma](https://invisiblenetwork.ai/learn/nptel/106106698/12cf4248ce5e) (Video) 35. [Introduction to Ramanujan graphs](https://invisiblenetwork.ai/learn/nptel/106106698/6492a0ea7d47) (Video) 36. [2-Lift and Zig-zag product for construction of expander and Ramanujan graphs](https://invisiblenetwork.ai/learn/nptel/106106698/f80f2b8bedac) (Video) 37. [Introduction of algebraic connectivity and Fiedler vector](https://invisiblenetwork.ai/learn/nptel/106106698/ee8369dcbf46) (Video) 38. [Upper bound on algebraic connectivity](https://invisiblenetwork.ai/learn/nptel/106106698/1c74ca533b17) (Video) 39. [Some more bounds on algebraic connectivity](https://invisiblenetwork.ai/learn/nptel/106106698/008f2e0d4cd2) (Video) 40. [Relation between algebraic connectivity of graph and its induced subgraph.](https://invisiblenetwork.ai/learn/nptel/106106698/7d67f3855c43) (Video) 41. [Introduction to Balanced Signed Graphs](https://invisiblenetwork.ai/learn/nptel/106106698/d6660b4a3126) (Video) 42. [Sign Switching in Signed Graphs](https://invisiblenetwork.ai/learn/nptel/106106698/e8bcd03879d8) (Video) 43. [Laplacian of Signed Graphs, Frustration number and Frustration index](https://invisiblenetwork.ai/learn/nptel/106106698/5fd3b1d9addb) (Video) 44. [Determinant, Permanent in terms of graph structure.](https://invisiblenetwork.ai/learn/nptel/106106698/59a66cf84239) (Video) 45. [Live Session 27-08-2025](https://invisiblenetwork.ai/learn/nptel/106106698/a49f03306d8a-2) (Video) 46. [Live Session 06-09-2025](https://invisiblenetwork.ai/learn/nptel/106106698/56a48cb62b6f-2) (Video) 47. [Live Session 22-09-2025](https://invisiblenetwork.ai/learn/nptel/106106698/aebc82a9b92e-2) (Video) 48. [Live Session 31-10-2025](https://invisiblenetwork.ai/learn/nptel/106106698/cb3c46f3caa0-2) (Video)