Let $G_1 = (V, E_1)$ and $G_2 = (V, E_2)$ be connected graphs on the same vertex set $V$ with more than two vertices. If $G_1 ∩ G_2 = (V, E_1 ∩ E_2)$ is not a connected graph, then the graph $G_1 U G_2 = (V, E_1 U E_2)$
- cannot have a cut vertex
- must have a cycle
- must have a cut-edge (bridge)
- has chromatic number strictly greater than those of $G_1$ and $G_2$
My attempt :
Somewhere, answer is given option $(2)$ , but it may be false , counter example is take line graph. It seems to option $(3)$ is true .
Can you explain please ?
Best Answer
A combined counterexample for (1), (3) and (4):
(2), on the other hand, is true, which is most easily seen on contraposed form: Suppose that $G_1\cup G_2$ has no cycle. Since it is connected, it must be a tree. But then removing even one edge from $G_1\cup G_2$ would make the resulting graph disconnected, so we must have $G_1=G_2=G_1\cup G_2$, and then $G_1\cap G_2=G_1\cup G_2$ is connected.
I don't understand how "take line graph" is would be a counterexample (or even what it means).