The Extremal Function for Two Disjoint Cycles

2015 
A theta graph is the union of three internally disjoint paths that have the same two distinct end vertices. We show that every graph of order \(n\ge 9\) and size at least \(\lfloor \frac{7n-13}{2}\rfloor \) contains two disjoint theta graphs. We also show that every 2-edge-connected graph of order \(n\ge 6\) and size at least \(3n-5\) contains two disjoint cycles, such that any specified vertex with degree at least three belongs to one of them. The lower bound on size in both is sharp in general.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    14
    References
    2
    Citations
    NaN
    KQI
    []