Bipartite graphs with balanced \((a,b)\)-partitions (Q2761049)

If \(a,b\) are two vertices of a graph \(G\), then \(C(a,b)\) denotes the set of all vertices of \(G\) whose distance in \(G\) from \(a\) is less than that from \(b\). Three conditions are considered: (B1) \(|C(a,b)|=|C(b,a)|\) for all adjacent pairs \(a,b\) in \(G\). (B2) \(G\) is bipartite. (B3) \(C(a,b)\) is convex for all adjacent pairs \(a,b\) in \(G\). The main theorem says that if a connected graph \(G\) with at least two edges satisfies (B1), (B2), (B3) and \(G\) is not a cycle, then \(G\) is 3-connected.