[Math] Union of two graphs

discrete mathematicsgraph theory

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)$

  1. cannot have a cut vertex
  2. must have a cycle
  3. must have a cut-edge (bridge)
  4. 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):

     A---B             A---B
      \ /               \ /
G1 =   C         G2 =    C
      /                   \
     D---E             D---E

(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).

Related Question