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
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
independent edges
0 references
connected graph
0 references
circuit
0 references