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 ?


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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.