Any four independent edges of a 4-connected graph are contained in a circuit (Q1073040)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Any four independent edges of a 4-connected graph are contained in a circuit
scientific article

    Statements

    Any four independent edges of a 4-connected graph are contained in a circuit (English)
    0 references
    0 references
    1985
    0 references
    L. Lovász raised the following conjecture: Suppose L is a set of k independent edges in a k-connected graph G (k\(\geq 2)\), and if k is odd then G-L is connected. Then G has a circuit containing all edges of L. This conjecture is proved for \(k=3\) by \textit{L. Lovász} [Combinatorial problems and exercises, North-Holland (1978; Zbl 0439.05001), {\S}6.67]. \textit{R. Häggkvist} and \textit{C. Thomassen} proved the same conclusion follows if G is \((k+1)\)-connected [Discrete Math. 41, 29-34 (1982; Zbl 0488.05048)]. In this paper, the authors prove the conjecture holds for \(k=4\).
    0 references
    0 references
    independent edges
    0 references
    connected graph
    0 references
    circuit
    0 references
    0 references
    0 references
    0 references