On the edge-connectivity of C4-free graphs

Research output: Contribution to journalArticlepeer-review


Let G be a connected graph of order n and minimum degree δ(G). The edge-connectivity λ(G) of G is the minimum number of edges whose removal renders G disconnected. It is well-known that λ(G) ≤ δ(G), and if λ(G) = δ(G), then G is said to be maximally edge-connected. A classical result by Chartrand gives the sufficient condition δ(G) ≥ n−21 for a graph to be maximally edge-connected. We give lower bounds on the edge-connectivity of graphs not containing 4-cycles that imply that for graphs not containing a 4-cycle Chartrand's condition can be relaxed to δ(G) ≥ q n2 +1, and if the graph also contains no 5-cycle, or if it has girth at least six, then this condition can be relaxed further, by a factor of approximately √2. We construct graphs to show that for an infinite number of values of n both sufficient conditions are best possible apart from a small additive constant.

Original languageEnglish
Pages (from-to)141-150
Number of pages10
JournalCommunications in Combinatorics and Optimization
Issue number2
Publication statusPublished - Jun 2019


  • Edge-connectivity
  • Maximally edge-connected

ASJC Scopus subject areas

  • Control and Optimization
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'On the edge-connectivity of C4-free graphs'. Together they form a unique fingerprint.

Cite this