Distribution of Contractible Edges and the Structure of Noncontractible Edges having Endvertices with Large Degree in a 4-Connected Graph

Abstract

Let G be a 4-connected graph G, and let Ec(G) denote the set of 4-contractible edges of G. We prove results concerning the distribution of edges in Ec(G). Roughly speaking, we show that there exists a set K0 and a mapping φ : K0 → Ec(G) such that |φ −1(e)| ≤ 4 for each e ∈ Ec(G).

Keywords

• 4-connected graph
• contractible edge
• cross free
• 05c40