2
$\begingroup$

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?

  • 5
    I'm pretty sure you're right.2012-08-31
  • 0
    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.2012-08-31

1 Answers 1