Counting maximal cycles in binary matroids

✍ Scribed by P. Hoffmann

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 68 KB
• Volume: 162
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(95)00240-w

✦ Synopsis

It is shown that each binary matroid contains an odd number of maximal cycles and, as a result of this, that each element of an Eulerian binary matroid is contained in an odd number of circuits. Let M be a binary matroid with circuits ~(M) and cycles .~(M), and let ~e(M) be the set of circuits containing an element e in the underlying set E(M). (For matroidtheoretical background see [113 Then M is Eulerian (: ¢:, E(M) e ~r(M)) iff # ~e(M) is odd for each e. Woodall [2] lists earlier occurrences of this statement and gives a new proof. The non-trivial part ('only if') can be reformulated ('each binary matroid contains an odd number of maximal cycles'), allowing another (simpler) proof. For S ~ E(M) let M\S denote the 'subtraction' of S with dement set E(M)\S and Cg(M\S)=~(M)c~(E(M)\S), and for eeE(M) let M\e=M{e}.