It is frequently said that Linear algebra is not correct until it is coordinate free or something to that effect and indeed, almost all the major results can be stated without picking a basis.
However, the application of linear algebra to graph theory seems impossible to make coordinate free. The definitions of the adjacency matrix, laplacian and proofs and results involving them are all stated in terms of the standard basis.
Is it possible to reformulate these results without reference to a basis. Is there some way of at least defining the Adjacency matrix (only upto an equivalence class of course) without picking basis?