0
$\begingroup$

This question already has an answer here:

let $n=\mid V\mid$

base case: let $n=0$. Thus lemma becomes vacuously true since both bipartitions will contain the empty set thus not a bipartite graph.

Inductive step:

let $k\in\mathbb{N}$, assume $P(k)$ show P(k+1): $\forall G=(V,E), k+1 = \mid V \mid\Rightarrow \mid E\mid\leq\frac{(\mid k+1\mid)^{2}}{4}$, where G is bipartite

I'm having trouble the inductive step, here's my intuition of how I think I should approach. create a subproof to show max possible edges in bipartite graph is when both bipartitions of V has the same size. Then we can assume if a bipartite graph is complete then proposition is satisfied for case 1. I think for Case two, prove for when # of edges are less than the max?

$\endgroup$

marked as duplicate by mrtaurho, Adrian Keister, Lee David Chung Lin, Sam T, blub Apr 12 at 18:20

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ math.stackexchange.com/questions/1098587/… $\endgroup$ – mathpadawan Apr 11 at 3:29
  • $\begingroup$ not sure if i'm approaching this correctly but case 1 when $\mid E \mid = \mid V1\mid\cdot\mid V2\mid$, where V1 , V2 are the bipartitions of V. Case 2, when $\mid E \mid < \mid V1\mid\cdot\mid V2\mid$ $\endgroup$ – neet Apr 11 at 3:44
0
$\begingroup$

There's no need to consider different cases to do the inductive step.

If for $k+1$ vertices $|E| \geq \frac{(k+1)^2}{4} +1$, remove a vertex with degree $ \leq \lfloor\frac{k + 1}{2}\rfloor$ (why does such a vertex exist?) to get a graph with $k$ vertices and more than $\frac{k^2}{4}$ edges, which contradicts $P(k)$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.