University of Illinois at Urbana Champaign Spring

University of Illinois at Urbana-Champaign Spring 2007 Math 181 Group F1 Midterm 1 : Correction. Friday, Feb. 23. 1. (a) Draw a graph with vertices A, B, C and D in which the valence of vertices A and D is 3 and the valence of vertices B and C is 2. A B C D (b) Is it possible to draw a graph on the same vertices in which A, B and C have valence 2 and D has valence 3 ? (explain). Answer. It is impossible, because the number of odd-valent vertices is always even. 2. For each of the graphs below, determine the minimal number of edges that need to be removed to disconnect it. Removing three edges is needed in order to disconnect this graph. One must remove 2 edges to disconnect this graph

• fit decreasing


• algorithm


• since there


• task time


• time needed


• when scheduling


• sorted-edges algorithm


• brute force


• euler circuit