标题： 可收缩非边在3-连通图中 显示英文标题

标题： Contractible Non-Edges in 3-Connected Graphs

摘要： 我们将图G中不相邻的顶点对称为非边。 在G中收缩一个非边{u，v}是用单个顶点z替换u和v，然后使所有与u或v相邻的顶点都与z相邻。 如果收缩后的图仍然是k-连通的，则称非边{u，v}在一个k-连通图G中是可收缩的。 Tsz Lung Chan在2019年刻画了所有不包含任何可收缩非边的3-连通图（有限或无限），并提出了刻画所有恰好包含一个可收缩非边的3-连通图的问题。 本文解决了这个问题。 显示英文摘要

摘要： We call a pair of non-adjacent vertices in G a non-edge. Contraction of a non-edge {u, v} in G is the replacement of u and v with a single vertex z and then making all the vertices that are adjacent to u or v adjacent to z. A non-edge {u, v} is said to be contractible in a k-connected graph G, if the resulting graph after its contraction remains k-connected. Tsz Lung Chan characterized all 3-connected graphs (finite or infinite) that does not contain any contractible non-edges in 2019, and posed the problem of characterizing all 3-connected graphs that contain exactly one contractible non-edge. In this paper, we solve this problem.