# Union of two graphs

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 ?

## 1 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).

• I misinterpreted problem, I were finding not common edges for both graphs . I'm reading your solution :) – 1 0 Nov 18 '15 at 10:56
• Why not option $(1)$ is true ? – 1 0 Nov 18 '15 at 11:01
• @MithleshUpadhyay: Counterexample updated. – Henning Makholm Nov 18 '15 at 11:05
• Thank you sir. Nice explanation . – 1 0 Nov 18 '15 at 11:07