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?

$\endgroup$
2
  • 5
    $\begingroup$ I'm pretty sure you're right. $\endgroup$
    – only
    Aug 31, 2012 at 0:18
  • $\begingroup$ 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. $\endgroup$ Aug 31, 2012 at 0:33

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ 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. $\endgroup$ Aug 31, 2012 at 0:33
  • 1
    $\begingroup$ Thank you, I was really confused. You assume that when they ask you to prove something, that it can be done. $\endgroup$
    – hobbes131
    Aug 31, 2012 at 0:33
  • $\begingroup$ @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$"). $\endgroup$ Sep 2, 2012 at 10:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .