Graph Theory Lessons

There are several ways to combine two graphs to get a third one. Suppose we have graphs G₁ and G₂ and suppose that G₁ has vertex set V₁ and edge set E₁; and that G₂ has vertex set V₂ and edge set E₂. The union of the two graphs, written G₁ U G₂ will have vertex set V₁ U V₂ and edge set E₁ U E₂.

Get the complete graph K₅ and save it as graph 1; then get the null graph N₁. Now click operations and union and when asked which graph to form a union with choose graph 1. You will get a graph like figure 21.

Fig. 21, K5 U N1.

The sum of the two graphs written G₁ + G₂ is obtained by first forming the union G₁ U G₂ and then making every vertex of G₁ adjacent to every vertex of G₂.

Get the graph N₁ again but this time click operations and sum and when asked which graph to sum N₁ with choose graph 1. You will get K₅ + N₁ as in figure 22. Save this graph as graph 2. Now get K₆ and check if it is isomorphic to graph 2.

Fig. 22, K5 + N1.

1. Which graph do you think is isomorphic to K_n + N₁?
2. Which graph is isomorphic to N_r + N₁?
3. Which graph is isomorphic to N_r + N_s?
4. Which graph is isomorphic to N_r U N_s?
5. Which graph is isomorphic to N_r + N_s + N_t?
6. Which graph is isomorphic to C_n + N₁? 

   ---

   We say that a graph is connected if it cannot be expressed as the union of two graphs; otherwise we say that it is disconnected. A disconnected graph can be expressed as the union of two or more connected subgraphs called components.

If you draw a graph in the applet below you will get a list of the components on the right side of the applet.



7. If X(G₁)=a and X(G₂)=b, then what is X(G₁ U G₂)? (You might have to do some experiments to give you some ideas)
8. If X(G₁)=a and X(G₂)=b, then what is X(G₁ + G₂)?

Answers