# IS and matching

I have 2 different but similar problems, one belongs to NP and one to L and I don't understand why.

First problem: Input: an undirected graph G with n^2 vertices. Question: Is there exist in G a matching of size n AND an independent set of size n?

Second problem: Input: an undirected graph G with n^2 vertices. Question: Is there exist in G a matching of size n OR an independent set of size n?

The AND problem is in NP and the OR problem is in L. Can someone explain why? Thanks.

• What have you tried? Where did you get stuck? We want to help you with your specific problems, but as it is we don't know what this problem is and thus how to help. See here for a relevant discussion. We expect you to make a significant effort before asking and to show us what you've tried. – D.W. Jan 23 '15 at 17:17

Hint for the first problem: Prove that it's NP-hard by reduction from independent set. Given a graph $G=(V,E)$ and a parameter $k \leq |V|$, add an independent set of size $|V|-k$ and a clique of size $|V|^2-|V| \geq 2|V|$ (the case $|V| < 3$ has to be handled separately), and connect all vertices of the clique to all other vertices.
Hint for the second problem: Suppose that $G$ doesn't have an independent set of size $n$. Show that it has a matching of size $n$ by dividing the $n^2$ vertices into $n$ sets of $n$ vertices, and picking an edge from each.