The path minimises the average size of a connected induced subgraph
John Haslegrave · Discrete Mathematics · 2022
We prove that among connected graphs of order n, the path uniquely minimises the average order of its connected induced subgraphs. This confirms a conjecture of Kroeker, Mol and Oellermann, and generalises a classical result of Jamison for trees, as well as giving a new, shorter proof of the latter. A different proof of the main result was given independently and almost simultaneously by Andrew Vince; the two preprints were submitted one day apart.