Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Determine whether the statements below are true or false. If the statement is true, then prove it; and if it is false, give a counterexample.

(a) Every disconnected graph has a vertex of degree 0.
(b) A graph is connected if and only if some vertex is connected to all other vertices.

Please correct me if i'm wrong. (a) is false, as we could have 2 triangles not connected with each other. The graph would be disconnected and all vertexes would have order 2.

(b) confuses me a bit. Since this is double implication, for the statement to hold, it must be:

A graph is connected if some vertex is connected to all other vertices. (true) AND Some vertex is connected to all other vertices if the graph is connected.

We could have a square. In this case the graph is connected but no vertex is connected to every other vertex. Therefore this part is false. Since this part is false - the whole statement must also be false.

Is this correct?

share|cite|improve this question
Everything you've said is correct. – Austin Mohr Apr 25 '13 at 2:12

So that this doesn't remain unanswered: Yes, all of your reasoning is correct.

share|cite|improve this answer
Nope, as it turned out it wasn't... part b was true – Supernatural May 14 '13 at 0:19

I know this is long overdue, but anyway the problem is that you have the definition of 'is connected to' incorrect. A vertex $u$ is connected to a vertex $v$ if there exists a $u-v$ path in $G$ (the graph containing $u$ and $v$). And a graph $G$ is connected if there exists a path between every two vertices of $G$. The way you have interpreted 'is connected to' in terms of vertices, you are really referring to adjacency.

so anyway using the correct definitions, (b) is clearly true.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.