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?

  • 3
    $\begingroup$ Everything you've said is correct. $\endgroup$ – Austin Mohr Apr 25 '13 at 2:12

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

  • $\begingroup$ Nope, as it turned out it wasn't... part b was true $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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