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

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?

-
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

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.
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.
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
@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