91Ó°ÊÓ

If 10 people each shake hands with each other, how many handshakes took place? What does this question have to do with graph theorv?

Is it possible for a planar graph to have 6 vertices, 10 edges and 5 faces? Explain.

Among a group of 5 people, is it possible for everyone to be friends with exactly 2 of the people in the group? What about 3 of the people in the group?

Which of the following graphs contain an Euler path? Which contain an Euler circuit? (a) \(K_{4}\) (b) \(K_{5}\). (c) \(K_{5,7}\) (d) \(K_{2,7}\) (e) \(C_{7}\) (f) \(P_{7}\)

For each degree sequence below, decide whether it must always, must never, or could possibly be a degree sequence for a tree. Remember, a degree sequence lists out the degrees (number of edges incident to the vertex) of all the vertices in a graph in non-increasing order. (a) (4,1,1,1,1) (b) (3,3,2,1,1) (c) (2,2,2,1,1) (d) (4,4,3,3,3,2,2,1,1,1,1,1,1,1)

Draw a graph with chromatic number 6 (i.e., which requires 6 colors to properly color the vertices). Could your graph be planar? Explain.

The graph \(G\) has 6 vertices with degrees 2,2,3,4,4,5 . How many edges does \(G\) have? Could \(G\) be planar? If so, how many faces would it have. If not, explain.

Is it possible for two different (non-isomorphic) graphs to have the same number of vertices and the same number of edges? What if the degrees of the vertices in the two graphs are the same (so both graphs have vertices with degrees \(1,2,2,3,\) and \(4,\) for example) \(?\) Draw two such graphs or explain why not.

For which \(n\) does the graph \(K_{n}\) contain an Euler circuit? Explain.

Is it possible for a graph with 10 vertices and edges to be a connected planar graph? Explain.