Graph Theory: True or False

Question

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.

Answer 1

(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?

Answer 2

(1) is false by counterexample from bof. (2) is like you say.

Concerning isomorphic graphs (3) and (4)

You should know that the term isomorphic literally means they are the same graph. All you have to do is move the vertices around and you get the same graph. So of course if $G$ and $H$ are isomorphic, then they are either both trees or both not, and they are either both connected or both not, because they are the same graph.

Concerning bipartite graphs (5)

Let $C_1, C_2, C_3, \ldots$ be the connected components of a graph $G$, and suppose they are bipartite with vertex sets $C_1 = A_1 \cup B_1, C_2 = A_2 \cup B_2, C_3 = A_3 \cup B_3, \ldots$, i.e. $A_i$ are the first part and $B_i$ are the second part of each connected component. Then you should be able to show that $A_1 \cup A_2 \cup \cdots$ and $B_1 \cup B_2 \cup \cdots$ form two disjoint sets of vertices whose union is $G$, and that this makes $G$ bipartite (no two vertices in $A_1 \cup A_2 \cup \cdots$ are connected by an edge, and same for $B_1 \cup B_2 \cup \cdots$).

Concerning regular trees (6)

This is true, because every tree has leaves. So you are correct.