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?
$\endgroup$ 12 Answers
$\begingroup$So that this doesn't remain unanswered: Yes, all of your reasoning is correct.
$\endgroup$ 1 $\begingroup$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.
$\endgroup$
