1. (a) Show that the graph in Figure 1 is planar (by drawing it without edge-crossings, and establishing that your drawing is the same graph as the one in Figure 1).

(b) Show that the graph in Figure 2 is not planar.

2. The algorithms we've discussed for finding minimal weight spanning trees in a weighted, undirected graph?can they be modified to find a maximal weight spanning tree in a weighted, undirected graph?

3. Find the chromatic polynomial i(G,k) for the graph G in Figure 3.

Transcribed Image Text:

Figure 1 D Figure 3 Figure 2 Figure 1 D Figure 3 Figure 2

Answer rating: 100% (QA)

1 Given that the graph is in planar 2 Yes we can modify an algorithm to find a maximal weight spanni... View the full answer