Interesting stuff. I had read about incidence matricies before, but hadn't seen a graph theory representation. By the way, I think there's an inconsistancy between your definition of the incidence matrix and the incidence matrix for C4 (did you mean m verticies and n columns, where the matrix is mxn?) Your graph of C4 also has the bottom two verticies interchanged.