Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose $G$ is a (simple) graph. A set of edges $M\!\subseteq\!E(G)$ is a matching if $\forall e,e'\!\in\!M:$ $e$ and $e'$ have no common vertex. A graph $H$ is bipartite if $\exists A,B\!\subseteq\!V(H)$ such that $A\cap B=\emptyset$, $V(H)=A\cup B$, and every edge in $H$ has one vertex in $A$ and one in $B$. A set of vertices $A\subseteq V(G)$ is an anticlique (i.e. "empty subgraph") if there are no edges in $G$ between vertices of $A$. Denote $n:=|V(G)|$ and $m:=|E(G)|$.

How can I prove the next statement:

PROBLEM: if $G$ has a matching with $k$ edges, then it has a bipartite subgraph $H$ with at least $(|E(G)+k|)/2$ edges.

Attempt of proof 1: I tried this with induction on $k$.

$k=m:$ this means that $G$ is bipartite, so $H:=G$ suffices. $\checkmark$

$m,\ldots,k\rightarrow k\!-\!1:$ Induction hypothesis: suppose we have a matching with $k-1$ edges in $G$ and suppose the claim is true for all matchings with at least $k$ edges. I don't know how to find an additional edge to add to the $(k-1)$-matching...

Attempt of proof 2: I have a very strong hunch this was meant to be solved via the probabilistic method (it was posted in the Probabilistic Method pack of problems). It would suffice to prove that if we randomly choose two anticliques $A,B\subseteq V(G)$, that the expected number of edges between $A$ and $B$ is $\mathbb{E}(|E[A,B]|)=(|E(G)+k|)/2$. It would then follow that there exists a choice of $A,B$ that has more than $(|E(G)+k|)/2$ edges. But I think randomly choosing any two anticliques will not suffice to get such a high expected value. Moreover, I don't know how to use the hypothesis about the existence of a $k$-matching...

any hints are very welcome

share|improve this question

2 Answers 2

up vote 4 down vote accepted

First of all, what you define as "clique" is usually known as an "independent set". A clique is usually defined as the graph containing all possible edges.

Second, the notion of subgraph you're using here is a "non-induced subgraph", meaning we just pick a subset of the edges. Often subgraph is "induced" by a set of vertices - you choose a subset of the vertices, and you get exactly the corresponding edges that belonged to the original graph.

Finally, here's how to solve it using the probabilistic method. Take your matching and assign the vertices randomly into the two bipartitions, under the condition that two vertices forming an edge get assigned to two different bipartitions. Divide the rest of the vertices completely randomly into the two bipartitions. Each non-matching edge has probability of exactly $1/2$ to have its endpoints in opposite sides, so the expected number of "legal" edges is $$k + \frac{|E|-k}{2} = \frac{|E|+k}{2}.$$


The construction can be derandomized. Suppose first $k=0$. We assign the vertices to bipartitions in some arbitrary order $v_1,v_2,\ldots$. When assigning $v_t$, we make sure that at least half the edges to earlier vertices $v_s,\; s<t$ are "legal" (this is always possible, exercise). The argument for $k > 0$ is similar.

This idea can be turned into a proof by induction on $k$. Prove the base case $k = 0$ in your favorite way. In order to move from $k$ to $k+1$, take one of the edges in the matching and contract it. Use the induction hypothesis to get a subgraph with lot of edges, and now split the vertex again. You have two choices for the position of the two endpoints, pick the one leading to more edges. Some accounting now leads to a proof.

The base case can also be proved by induction - just present the proof in the first paragraph (for the case $k=0$) as a proof by induction.

share|improve this answer
    
sorry for the clique confusion, I corrected it now –  Leon Lampret Jul 31 '11 at 20:37
    
as for the subgraph issue, the problem just states subgraph, so yes, a subset $V(H)\subseteq V(G)$ and a subset $E(H)\subseteq E(G)\cap\binom{V(H)}{2}$ –  Leon Lampret Jul 31 '11 at 20:39
    
Concerning the third paragraph (probabilistic solution): If I understand correctly, the expected value being $(|E(G)|\!+\!k)/2$ means there exists a partition of $V(G)$ into $A$ and $B$ with at least $(|E(G)|\!+\!k)/2$ edges with endpoints in different $A$ and $B$. So $H$ is then those $(|E(G)|\!+\!k)/2$+ edges, right? –  Leon Lampret Aug 1 '11 at 3:46
    
anyway, thank you very much for a very insightful answer :) –  Leon Lampret Aug 1 '11 at 15:41
    
Your interpretation is correct. If the expectation of a random variable is $E$, then it sometimes gets values at least as large as $E$. –  Yuval Filmus Aug 1 '11 at 19:07

I have an idea how to prove it without the probabilistic method though. I would try to start out with the matching as a bipartite graph and successively add the other vertices and some of the edges that are connected to the existing bipartite subgraph. If the vertices included in the matching werent connected other than the matching that would be it and easy. But you actually have to start out earlier "turning" the matchings the right way and add them successively first.

I notice this sounds a little cryptic. I can try to write down a full solution if you want it, but you asked for a hint at first.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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