For the graph of exercise 2, I found a,b,e,d,z. Therefore the total weight is 7. It is the shortest path. --rtabchou
I'm not sure you are on the right problem. We need to determine if the graph is planar which it is not by corollary 3 of theorem 1 as 2*v-4=8 which is less than e=9. You can use this corollary since there are no circuits of length 3.
You can also look at the graph and see that it is a representation of K(3,3), and therefore, is not planar.
