1) Draw a simple directed graph with 7 vertices and 9 edges.

 

2) Draw a bipartite graph with 5 vertices and 6 edges, then show it is bipartite by using the “coloring” method.

 

3) Draw a graph which is not bipartite with 5 vertices and 8 edges, then show it is not bipartite by using the “coloring” method.

 

4) How many vertices and how many edges do these graphs have? No need to justify.

 

5) A simple graph is called regular if every vertex of this graph has the same degree.

1. a) For which values of n is regular?
2. b) For which values of n is regular?
3. c) For which values of n is regular?

 

Note: in each case you have a regular graph, say what is the degree of each of its vertices. No need to justify your answer.

Hint: try some small cases first so you can guess the general formula in each case.

 

6) Determine which of the following sequences is graphic (that is to same it is possible to draw a graph with the given sequence). For those that are, draw a graph having the given degree sequence.

 

1. a) 4,4,3,3,3
2. b) 3,2,2,1,0

 

7) Suppose that a new company has five employees: Zamora, Agraharam, Smith, Chou, and Macintyre. Each employee will assume one of six responsibilities: planning, publicity, sales, marketing, development, and industry relations. Each employee is capable of doing one or more of these jobs: Zamora could do planning, sales, marketing, or industry relations; Agraharam could do planning or development; Smith could do publicity, sales, or industry relations; Chou could do planning, sales, or industry relations; and Macintyre could do planning, publicity, sales, or industry relations.

 

1. a) Model the capabilities of these employees using a bipartite graph.
2. b) Find an assignment of responsibilities such that each employee is assigned one responsibility.
3. c) Is the matching of responsibilities you found in part (b) a complete matching? Is it a maximum matching?