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?
Best Answer
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.