1
$\begingroup$

I've come across a question that has got be stuck for hours. I need to proof that:

Let $G$ be a graph $=(V,E)$, a bipartite graph with $n$ vertices and $e$ edges. Show that $$e\leqslant \left\lceil \frac{n}{2} \right\rceil \cdot \left\lfloor \frac{n}{2} \right\rfloor\;.$$

I can't understand that even though this graph

enter image description here

qualifies as bipartite, it doesn't follow the equation showed above.

Any helps would be appreciated.

p.s the red dots indicate a vertex. Sorry if it isn't clear, my paint skills arent top of the art.

$\endgroup$
1
$\begingroup$

That graph is $K_4$, the complete graph on $4$ vertices; it’s not bipartite. Remember, two vertices in the same part of a bipartite graph are not connected by an edge. In $K_4$ every pair of vertices is connected by an edge, so no two vertices could be in the same part.

HINT: Suppose that $G=\langle V,E\rangle$ is a bipartite graph on $n$ vertice, and let $A$ and $B$ be the two parts of $V$, so that $E$ is the set of edges $v_0v_1$ with $v_0\in A$ and $v_1\in B$. Let $a=|A|$ and $b=|B|$; then $e=ab$. (Why?) To prove the result, you need to show that $a$ and $b$ are positive integers whose sum is $n$, then $$ab\le\left\lceil\frac{n}2\right\rceil\left\lfloor\frac{n}2\right\rfloor\;.\tag{1}$$

If $n$ is even, say $n=2m$, then $(1)$ is just $ab\le m^2$, and since $a+b=n$, you can even simplify it to $a(2m-a)\le m^2$. That inequality can in turn be written $m^2-2am+a^2\ge 0$. Can you simplify the lefthand side in a way that shows that this inequality is always true? Once you’ve done that, you’ll have shown that $(1)$ is true when $n$ is even.

To finish the proof, suppose that $n$ is odd, say $n=2m+1$. Now express $\left\lceil\frac{n}2\right\rceil$ and $\left\lfloor\frac{n}2\right\rfloor$ in terms of $m$, and try to make a similar argument.

$\endgroup$
0
$\begingroup$

The graph you've drawn is not bipartite; remember, a bipartite graph is a graph whose vertex set can be split in to two nonempty parts $A$ and $B$, so that all edges in the graph are incident to exactly one vertex of $A$ and one vertex of $B$ - there are no edges which have either both endpoints in $A$ or both endpoints in $B$.

In the graph you've drawn: any bipartition will have either $\lvert A\rvert\geq2$ or $\lvert B\rvert\geq2$; but, since every two vertices are connected by an edge, this cannot be accomplished without having edges inside one of the sets.

As for proving the result in question, let me give you the following hint: if $(A,B)$ is a bipartition of the graph - that is, $A\cap B=\emptyset$ and $A\cup B=V(G)$, and no edge has either both endpoints in $A$ or both endpoints in $B$ - then the largest number of possible edges is $\lvert A\rvert\cdot\lvert B\rvert$. Why?

Once you have this, note that $\lvert A\rvert+\lvert B\rvert = n$; among all of the ways you can choose two positive integers that add to $n$, which one makes their product as large as possible?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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