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?

  • 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

5

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.

  • 0
    @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$").2012-09-02