Counterexamples to a conjecture of Mader about cycles through specified vertices in \(n\)-edge-connected graphs (Q1199122): Difference between revisions

Providing counterexamples to a conjecture of Mader, the following theorem is proven: If \(n\geq 3\) is odd, then there exists an \(n\)-edge-connected graph \(G\) of order \(2^{(n+3)/2}\) which contains two vertices \(u\) and \(v\) at distance three such that, for each cycle \(C\) passing through \(u\) and \(v\), \(G-E(C)\) is not \((n-2)\)-edge-connected.