Talk:Mac Lane's planarity criterion

The proof states that the cycle space for the complete K5 is 7-dimensional, however for a connected graph isn't the dimension of the cycle space |E|-|V|+1 = 10-5+1=6? This formula is given in the page, Cycle_space for cycle space whether over GF(2) or the rationals. That is the rank of the |V|×|E| incidence matrix, M, of a connected graph (V,E) is |V|-1 so the right null space (the cycle space) has dimension |E| - rank(M) =|E|-|V|+1. Likewise the proof states that the cycle space of K3,3 is 5-dimensional, however 9-6+1=4 dimensions. If C(G) for K5 is 6-dimensional then there would be only at least 18 non-zeros rather than 21 on which the proof depends. Likewise for K33 there would be only at least 16 non-zeros instaed of 20 on which the proof depends also.

It's easy enough to patch the proof. If you have a cycle basis that uses each edge at most twice, it must cover some edges exactly once (else the sum of all the basis members would be zero, not possible for the basis), and the GF2 sum of the basis elements must form another even subgraph. So together with any set of basis cycles you can get one more non-basis cycle. Unfortunately it's difficult to tell whether this is original research or follows the original lines of thought of the sources. In order to make the case that his proof was short, O'Neil left out all the important definitions and instead referred to Mac Lane for them. Do we know of an online version of the Mac Lane paper or is this going to have to involve going to one of those big buildings with all the books in them? —David Eppstein (talk) 18:18, 7 March 2012 (UTC)

Ok, I found Mac Lane's paper online and added the url. But the solution appears to be within O'Neil after all — he defines the last of the circuits to be the sum of the other ones. —David Eppstein (talk) 21:35, 7 March 2012 (UTC)

Thanks for clarifying. The reference to Lefschetz is interesting but the Peterson Graph has a cycle double cover and in GF2 the sum of all these would be zero. Orientabilty of the face cycles must be captured in the integral cycle space where +1 <> -1. --StephenK51 (talk) 16:13, 8 March 2012 (UTC)