Georgia Institute of Technology College of Sciences

A characterization of graphs without an odd cycle is easy, of course,it is exactly bipartite. However, graphs without two vertex disjoint oddcycles are not so simple. Lovasz is the first to give a proof of the twodisjoint odd cycles theorem which characterizes internally 4-connectedgraphs without two vertex disjoint odd cycles. Note that a graph $G$ iscalled internally 4-connected if $G$ is 3-connected, and all 3-cutseparates only one vertex from the other.However, his proof heavily depends on the seminal result by Seymour fordecomposing regular matroids. In this talk, we give a new proof to thetheorem which only depends on the two paths theorem, which characterizesgraphs without two disjoint paths with specified ends (i.e., 2-linkedgraphs). In addition, our proof is simpler and shorter.This is a joint work with K. Kawarabayashi (National Institute ofInformatics).