1. $A^{k}_{ij}$ counts the $k$-paths from $i$ to $j$. This is what got me hooked on algebraic graph theory in the first place.
2. Fielder's algebraic connectivity <= vertex connectivity.
3. The relations between vertex connectivity and isoperimetric number.
4. Lovasz's bound on Shannon capacity.
5. The classification of generalized line graphs.