|
Post by vsiap on Dec 1, 2014 17:03:39 GMT
Suppose that G is a connected, simple graph with V (G1) ∪ V (G2) = V (G), E(G1) ∪ E(G2) = E(G), and E(G1) ∩ E(G2) = φ. We need to show that V (G1) ∩ V (G2)<>(not equal) φ. We prove by contradiction. Suppose V (G1) ∩ V (G2) = φ. Then there does not exist u,v such that u ∈ V(G1), v ∈ V(G2) and (u,v) ∈ E(G) (otherwise the edge would have been part of one of G1 or G2, and its one end point would be common to both. ⇒ ∃x,y, x ∈ V(G1), y ∈ V(G2) such that there is no path between x and y ⇒ G is not connected. This is a contradiction.
|
|