[Math] Graph Theory: True or False

graph theory

A couple of True/False problems I am working through. No full proof is required just whether the statements are valid or not.

1) If $G$ contains a closed walk, then $G$ contains a cycle.

False

2) Let $G$ be a connected graph. If $G$ has no bridges, then $G$ has no cut vertices.

False. A counterexample is pretty easy to generate; two triangles with a common vertex will yield a graph with 5 vertices and 6 edges that contains 1 cut vertex and no bridges.

3) Suppose $G$ and $H$ are isomorphic graphs. If $G$ is a tree, then $H$ is a tree.

True

4) Suppose $G$ and $H$ are isomorphic graphs. If $G$ is connected, then $H$ is connected.

True

5) If every connected component of $G$ is bipartite, then $G$ is bipartite.

True

6) If $G$ is a regular tree, the $G$ is $K_1$ or $K_2$.

True.

Best Answer

(1) is false. A cycle is a closed walk with no repeated vertices except for ending up at the vertex where it started. The $2$-point path $P_2$ has a closed walk (walk from one end to the other and back again) but no cycles.

(5) is true. (It may help to recall that a graph is bipartite if and only if it's $2$-colorable. More generally, a graph is $n$-colorable if and only if every connected component is $n$-colorable.)

The rest of your answers are correct. The fact you're not sure about the answers to (3) and (4) is a little troubling. Maybe you aren't quite clear on the concept of isomorphism?

Related Question