MATH 180 Midterm: Math 180 Exam 4
Document Summary
This test is closed book and closed notes. For full credit show all of your work and (brie y) explain your approach (legibly!). Suppose that we have a bridge, i. e. , then our picture is like the following. Look at the graph corresponding to these vertices and edges. Where we have vertices on the left and right and one edge going between the two sets. Examining the graph found by looking at the vertices and edges of the left part we see that we will have one vertex of degree k 1 (odd) and all other vertices would have degree k (even). But this is impossible because the number of vertices with odd degree must be even. Therefore our assumption that we have a bridge must be wrong, and so there is no bridge. (b) give an example of a graph with 10 vertices which is regular of degree 3 and has a bridge.
