STOR 215 Sample Questions for Final Here are some sample questions for the nal exam questions on the actual nal will be di erent Remember that the nal exam is comprehensive these questions only concern the material on graphs All exams in the course are closed book and closed notes and calculators are not permitted Most questions will have multiple parts and in many cases di erent parts of the same question are unrelated so if you cannot solve one part of a question you should still try the other parts 1 Let G V E be an undirected graph De ne cut vertex When is G biparatite 2 Carefully de ne what it means for two graphs G1 V1 E1 and G2 V2 E2 to be isomorphic De ne the notion of an isomorphism invariant Given an example of an isomorphism invariant 3 Draw the graphs K2 2 C4 and K3 Find the chromatic number of each graph 4 An undirected graph G has the following adjacency matrix 0 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 Draw the graph G Is G connected Does G have a cut vertex Does G have a Hamilton path 5 Let G be a simple graph and let u be a vertex in G Show that if there is a circuit c from u to u then there is a simple circuit from u to u 6 A connected simple planar graph G with 9 vertices divides the plane into 3 regions How many edges does G have 7 Let G V E be a bipartite graph with vertex partition V V1 V2 Hall s theorem gives necessary and su cient conditions for the existence of a complete matching from V1 to V2 Carefully state these conditions 8 A simple graph G V E has four vertices The following are possible sequences of degrees for the vertices in V In each case draw a graph with the given degree sequence or say why no such simple graph exists a 1 1 0 0 b 2 1 0 0 c 4 1 1 0
View Full Document