MathCastle
Graph TheoryMediumWalks, Paths and Connectivity

Walks, Paths and Connectivity · Medium problem

A graph on vertices 1,…,91,\ldots,9 consists of a 66-cycle 1-2-3-4-5-6-11\text{-}2\text{-}3\text{-}4\text{-}5\text{-}6\text{-}1 together with three pendant vertices: 77 attached to 11, 88 attached to 33, and 99 attached to 55. If vertex 11 is deleted, what is the size of the largest resulting connected component?