The induced bipartite subgraph number of a finite simple
graph
is the largest number of vertices
in an induced subgraph which is a bipartite
graph. It is also called the bipartite number (DeLaVina 2026). Equivalently,
is the maximum size of a union of two disjoint independent
vertex sets. In particular,
exactly when
is a bipartite graph.
For a connected graph with at least two vertices, write
for the average graph eccentricity, and let
|
(1)
|
where
is the open graph neighborhood and
is the independence number of
. Chen et al. (2026) proved
|
(2)
|
where
is the floor function. This proves conjecture 19
of Written on the Wall II. Their argument also recovers the earlier bound
|
(3)
|
where
is the graph diameter. This bound was proved by
DeLaVina and Waller (2004, as recorded by DeLaVina 2026). The first bound is sharp
for complete graphs and star
graphs.
Sadeghi (2026) gives a separate Lean proof of the average-eccentricity bound and reports substantive proof assistance from Gemini. Its published Palomar Registry record reports successful kernel acceptance. The earlier proof of Chen et al. (2026) was posted on July 2, 2026.