The poset on connected induced subgraphs of a graph need not be Sperner

摘要

SupposeGis a finite connected graph. LetC(G) denote the inclusion ordering on the connected vertex-induced subgraphs ofG. Penrice asked whetherC(G) is Sperner for general graphsG. Answering Penrice's question in the negative, we present a treeTsuch thatC(T) is not Sperner. We also construct a related distributive lattice that is not Sperner.