# disconnected/connected graphs

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?

• Everything you've said is correct. – Austin Mohr Apr 25 '13 at 2:12

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.