Algebraic Methods (Lecture 1 & 2)

Q) Given a graph \(G\) that does not contain any 3-cycle or 4-cycle, with degree of each vertex as \(r\), what is the minimum number of vertices possible for \(G\)?

A) Draw a picture to see the proof and verify with the notes linked above.

Q) For what value of \(r\) does the graph with \(r^2 +1\) vertices exist?

A) Need to use results from Linear Algebra because the main character in the solution is the Adjacency Matrix.