MathCastle
Graph TheorySuperchallengeWalks, Paths and Connectivity

Walks, Paths and Connectivity · Superchallenge problem

A connected graph on 1010 vertices must stay connected after removing ANY 22 of its vertices (that is, κ(G)≥3\kappa(G) \ge 3). What is the fewest edges such a graph can have, and does the Petersen graph (outer 55-cycle, inner pentagram, and 55 spokes joining them: 33-regular on 1010 vertices) achieve it?