Existence of a path of length n/2 in every bipartite graph with
Claim: Let be a balanced bipartite graph with then G has a path of length n/2.
I know about the erdos-gallai theorem that would net a path of length n/4. By noting that
I suspect that the condition of being bipartite forces the ecistence of a longer path, and I am yet unaware of such a result or a counterexample.
Part of my intuition is from the fact that considering a disjoint union of 2 copies of which are edge-maximal biparite graphs not containing such a path, we then have these two subgraphs and two yet to be connected vertices on A, also:
And adding any edge would form a path of the desired length. Any help on how to go about proving this, or a reference for such a resukt would be greatly appreciated.