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.

Consider a graph G such that at least one vertex v is connected to all other vertices. Prove that G is not bipartite.

That's the question, however, I don't think it can be proven. I think there's something wrong with the question but I'm not sure.

what if you had a graph with three vertices A,B,C and there were edges A-B and A-C. Vertex A would be connected to all other vertices and yet the graph is still bipartite based on the two color theorem.

Am I missing something here?

share|improve this question
5  
I'm pretty sure you're right. –  only Aug 31 '12 at 0:18
    
Are you sure you are not missing any other conditions (such as the number of edges)? There are many counterexamples to the claim as stated. –  Austin Mohr Aug 31 '12 at 0:33

1 Answer 1

There are infinitely-many counterexamples to the claim as stated. Consider the graph on $n+1$ vertices where $v$ is connected to each of the other $n$ vertices but no other edges are included (this is sometimes called the star graph $S_{n+1}$). The graph is bipartite: put $v$ in one set and the remaining $n$ vertices in another.

star graphs

As noted in the comments, these are the only counterexamples to the claim. A graph is bipartite if and only if all of its cycles have even length. If $S_{n+1}$ is given even one more edge, it will contain a cycle of length three, and so will not be bipartite.

share|improve this answer
3  
However, these are the only counterexamples. If the graph contains at least one edge that is not incident on the vertex $v$, then it is not biparite. –  Nate Eldredge Aug 31 '12 at 0:33
    
Thank you, I was really confused. You assume that when they ask you to prove something, that it can be done. –  hobbes131 Aug 31 '12 at 0:33
    
@hobbes131 Yes, you normally do. Then again even problem posers make mistakes, and even with a correct problem statement one might get insights into proof strategies by (first?) trying to find counterexamples (like "Aha, that's why he adds 'not a tree' as condition"). In my days, submitting a counterexample showing that the claim as exactly stated was wrong gave full score just as did a correct proof for the claim corrected by additional "obvious" but left-out conditions (e.g. by replacing "set $A$" by "non-empty set $A$"). –  Hagen von Eitzen Sep 2 '12 at 10:13

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.