A lower bound for the convexity number of some graphs (Q1428997)

A set \(C\) of vertices in a connected graph \(G\) is called convex if for all \(x,y\in C\) all vertices of each shortest \(x\)-\(y\)-path are in \(C\). The convexity number of \(G\) is defined to be the cardinality of a maximal proper convex set in \(G\). The main result of the paper reads: for all integers \(k\) and \(n\) satisfying \(2\leq k\leq n-1\) there is a connected triangle-free graph with \(n\) vertices whose convexity number is \(k\).