TOPICS
Search

Induced Bipartite Subgraph Number


The induced bipartite subgraph number b(G) of a finite simple graph G 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, b(G) is the maximum size of a union of two disjoint independent vertex sets. In particular, b(G)=|V(G)| exactly when G is a bipartite graph.

For a connected graph with at least two vertices, write epsilon^_(G) for the average graph eccentricity, and let

 lambda(G)=max_(v in V(G))alpha(G[N(v)]),
(1)

where N(v) is the open graph neighborhood and alpha(H) is the independence number of H. Chen et al. (2026) proved

 b(G)>=|_epsilon^_(G)+lambda(G)_|,
(2)

where |_x_| is the floor function. This proves conjecture 19 of Written on the Wall II. Their argument also recovers the earlier bound

 b(G)>=diam(G)+lambda(G)-1,
(3)

where diam(G) 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.


See also

Bipartite Graph, Graph Eccentricity, Independence Number, Induced Subgraph

Explore with Wolfram|Alpha

References

Chen, Z.; Wang, Q.; and Feng, Y. "A Source-Scoped Lean-Verified Proof of WOWII Conjecture 19." 2 Jul 2026. https://www.preprints.org/manuscript/202607.0114.DeLaVina, E. "Written on the Wall II: Conjectures of Graffiti.pc." 2026. https://www.uhd.edu/academics/sciences/mathematics-statistics/wowii/index.html.Sadeghi, H. "Written on the Wall II Conjecture 19: Lower Bound on the Largest Induced Bipartite Subgraph Size from Average Eccentricity and Neighborhood Independence." Palomar Registry, 2026. https://palomar-registry.org/entry.html?id=PALOMAR-2026-11-16-000014&version=1.

Cite this as:

Weisstein, Eric W. "Induced Bipartite Subgraph Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/InducedBipartiteSubgraphNumber.html

Subject classifications