Contractible Edges and Contractible Triangles in a 3-Connected Graph

Let G be a 3-connected graph. An edge (a triangle) of G is said to be a 3-contractible edge (a 3-contractible triangle) if the contraction of it results in a 3-connected graph. We denote by \(E_{c}(G)\) and \(\mathcal {T}_{c}(G)\) the set of 3-contractible edges of G and the set of 3-contractible triangles of G, respectively. We prove that if \(|V(G)|\ge 7\), then \(|E_{c}(G)|+ \frac{15}{14}|\mathcal {T}_{c}(G)|\ge \frac{6}{7}|V(G)|.\) We also determine the extremal graphs.

The authors would like to thank Professor Katsuhiro Ota for his valuable comments. The authors are also grateful to the referee, whose suggestions have greatly improved the presentation of the paper. This work is supported by JSPS KAKENHI Grant Number JP18H05291.

Authors and Affiliations

1. National Institute of Informatics, Global Research Center for Big Data Mathematics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo, 101-8430, Japan

   Kiyoshi Ando

2. Department of Applied Mathematics, Tokyo University of Science, 1-3 Kagurazaka, Shinjuku-ku, Tokyo, 162-8601, Japan

   Yoshimi Egawa

Corresponding author

Correspondence to Kiyoshi Ando.

Dedicated to Professor Hikoe Enomoto and Professor Ei-ichi Bannai on the occasion of the 75th anniversary of their birth.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Reprints and permissions