I get that lin alg maybe isn't your picture of elegance, but you can't say that proof is laborious or esoteric. Any intro-level LA course is enough to grok it.
No, Lin-Alg is in fact what I work on in my research on spectral graph theory and graph partitions for approximation algorithms; but I do think there are different tools for different jobs.
There are plenty of interesting results where linear algebra shines and is beautiful (Kirchoff's theorems for counting trees, random walks on lattices as electrical networks, harmonic functions on graphs, topological data analysis) but there's plenty of statements where linear algebra is a hammer that's wholly unnecessary---statements that are already simple or elegant using other descriptions of graphs.
Though: interesting paper you linked to, thanks for that.
I get that lin alg maybe isn't your picture of elegance, but you can't say that proof is laborious or esoteric. Any intro-level LA course is enough to grok it.