Properties of the union of two connected graphs, if their intersection is not connected

Question

Let G1=(V, E1)and G2=(V, E2) be connected graphs on the same vertex set V with more than two vertices. If G1∩G2=(V, E1∩E2) is not a connected graph, then the graph G1∪G2=(V, E1∪E2)

a)cannot have a cut vertex.

b)must have a cycle

c)must have a cut-edge (bridge)

d) Has chromatic number strictly greater than those of G1 and G2

=========================================================================

Correct answer is the option (b)

=========================================================================

My Approach is:

The thing is I'm getting option a) also correct the way I choose the graph. So, How I would be sure in Exam what Graph to take so I get a correct answer as you can see here right answer is option b), but I'm also getting a) correct.

Answer 1

To actually prove that G1 ∪ G2 contains a cycle.

There are two cases to consider, first the trivial case:

If either G1 or G2 contain a cycle, then G1 ∪ G2 must have a cycle - the cycle that existed in G1 or G2.

The more interesting case is when both G1 and G2 are acyclic.

Some (hopefully) already established facts about any connected acyclic undirected graph G = (V,E) :

• There is exactly 1 path between every pair of vertices (V1 ∈ V, V2 ∈ V), V1 ≠ V2.
• |E| = |V| - 1.

So for G1 and G2 both being acyclic and connected, they both contain |V| - 1 edges. Because G1 ∩ G2 is not connected, they must not be G1 = G2, there must be an edge that exists in G2 that does not exist in G1.

Consider this edge Ek = (Vi, Vj) such that (Vi, Vj) ∉ E1 and (Vi, Vj) ∈ E2

The graph G1 ∪ G2 contains the path from Vi to Vj that is in G1 because it contains all of the edges in G1. Because G1 does not already contain Ek, including it (from G2) creates a cycle including the path from Vi to Vj in G1, and the edge Ek, therefore G1 ∪ G2 must contain a cycle.

Answer 2

If your goal was to disprove by counter-example, then you got off to a good start with a simple graph with 3 vertices.

Such a graph meets the requirements that G1 and G2 are connected, and the intersection is not connected. However, the union only disproves answer c). Specifically, the union

• does not have a cut vertex, so a) is allowed
• does have a cycle, so b) is allowed
• does not have a cut-edge, so c) is eliminated
• has chromatic number 3, whereas G1 and G2 have chromatic number 2, so d) is allowed

The next step is to realize that d) is almost certainly wrong. The reason: it's easy to add nodes to a graph without changing its chromatic number. Which is to say that it should be easy to find an example where G1 and G2 are three colored, and the union is also three colored.

So that leaves you with a) or b).
If you guess that a) is wrong, then you need to find a graph that has a cut vertex, and has a cycle.
If you guess that b) is wrong, then you need to find a graph that does not have a cut vertex, and does not have a cycle.

Guessing that b) is wrong is a little problematic, because a graph with no cycles is a tree or a path, and trees and paths are full of cut vertices.

So the next step is imagine a graph that has a cut vertex. The first such graph that came to me is the hourglass:

Once again, G1 and G2 are connected, and the intersection is not connected. This time, the union disproves three of the answers. Specifically, the union

• does have a cut vertex, so a) is eliminated
• does have a cycle, so b) is allowed
• does not have a cut-edge, so c) is eliminated
• has chromatic number 3, and G1 and G2 also have chromatic number 3, so d) is eliminated

Note that we haven't proven b) is correct, only that a) c) and d) are definitely incorrect, so b) is the answer by elimination.