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.

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|improve this question
add comment

1 Answer

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|improve this answer
1  
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
1  
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
1  
@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
add comment

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.