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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A graph is called to be factor-critical if $G-v$ has a perfect matching for any vertex $v$ of $G$. Prove that a bipartite graph is never factor-critical.

share|cite|improve this question
up vote 2 down vote accepted

Let's suppose that $G$ is bipartite, then I guess just let its two color classes consist of $m$ and $n$ vertices with the property such that $m\leq n$.

There's no way we can omit any vertex from the color class that's with $m$ elements so that resulting graph has a perfect matching.

$\therefore$We would get a bipartite graph with two color classes of different size.

share|cite|improve this answer
Another question, how to prove that $G$ is factor-critical if and only if $G$ has an odd number of vertices and $c_o (G-S)\leq |S|$ for all nonempty set $S$ of vertices – user68067 Mar 22 '13 at 20:57
Hey dude I can't just do all the homework for you try to figure out yourself – user67258 Mar 22 '13 at 21:00
Well I'm having trouble – user68067 Mar 22 '13 at 21:09
@user68067 If this is a new question then either edit the original post or start a new question. Also, please show what you've tried. – TakeS Mar 22 '13 at 21:15
Yes exactly, this is not Chegg lmao – user67258 Mar 22 '13 at 21:26

Your Answer


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.