A note on the size of edge-chromatic 4-critical graphs

In 1968, Vizing conjectured that for any ΔΔ-critical graph GG with nn vertices and mm edges, m≥12[(Δ−1)n+3]. Miao and Pang (2008) proved that m≥74n when Δ=4Δ=4. However, their proof has a gap. In this paper, we first prove a new adjacency lemma and then apply this lemma to fix the gap.