Removable edges in a 5-connected graph and a construction method of 5-connected graphs (Q2477398): Difference between revisions

Let \(e\) be an edge of a k-connected graph. Let \(H\) be the graph obtained from \(G\) by removing \(e\) from \(G\), and for any end vertex \(x\) of \(e\) with degree \(k-1\) in \(G-e\), delete \(x\) and then add edges between any pair of non-adjacent vertices in the neighbour set of \(x\) in \(G-e\). If \(H\) is k-connected then e is said to be a removable edge of \(G\). The authors prove that a 5-connected graph has no removable edge if and only if it is isomorphic to \(K_6\). For a k-connected graph \(G\) such that end vertices of any edge of \(G\) have at most \(k-3\) common adjacent vertices, the authors prove that \(G\) has a removable edge.