Given a simple graph $G$ with $n$ vertices. Prove that there exist simple graphs $S_1,\ldots,S_k$ with $k\leq\frac34n$, such that every $S_i$ is a complete bipartite graph, every edge of $G$ is contained by an odd number of graphs $S_i$, and every edge of the complement of $G$ is contained by an even number of graphs $S_i$.

If we didn't have the condition $k\leq \frac34n$, we could pick the graphs $S_i$ with every edge being one graph. But the number of edges can be as large as $\frac{n(n-1)}{2}$. Maybe we can find an inductive algorithm to construct $S_1,\ldots,S_k$?


Your Answer

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

Browse other questions tagged or ask your own question.