1. On this assignment, you are required to use an
applet (see assignments below). The applet contains several graphs. You
will need to include a drawing of your graphs in your Maple file in order to
receive full credit. The reason for this is that the graphs appear in a
randomized order and so your 1st graph may be different than mine. Thus, you
need to have a graph and a response to the question for each exercise. Do not
say that 3 graphs were circuits and 2 were not (and do not say that graphs 1,
2, 3 were circuits and the others were no), as this will not earn full credit.

Section
9.1

1. In a company, emails
sent from one employee to another are tracked as follows: Mr. Cooper sends 3
emails to Mrs. Sanders.
Mrs. Sanders sends 4 emails to Ms. Bighton, Ms. Bighton send 1 email to
Mr. Ortega and Mr. Ortega
does not send anyone any emails. Furthermore, Mrs. Sanders sends Mr.
Cooper 3 emails, Mrs. Bighton sends Mr.
Cooper 2 emails.
(a) Draw a graph to
represent connections within this company, based on email data, where each
vertex represents a person
and an edge joining two vertices represents thepresence
of email communication, and the absence of an edge indicates the absence of
email communication (irrespective of
direction).No need to try to draw edges to
indicate absence of communication.

(b) Find the beta index of the graph you
found in part (a).
2. You and a friend meet three other couples
at a party and several handshakes take place.
Nobody shakes hands with himself or herself, there are no handshakes
within couples, and no oneshakes hands with the same person more than
once. The number of hands shaken by the
other seven people (excluding you) are all different. How many hands did you shake? How many hands did your partner shake? Use a graph to aid your solution.
Section
9.2:

1. Draw a pseudograph to
represent the email communication graph described in exercise 1 (Section 9.1)
above. In your
pseudograph, each vertex represents a person and an directed edge joining two
vertices
represents an email sent.
2. Verify Proposition 9.2.5 and Corollary
9.2.6 for the pseudograph you found in the previous exercise.

4. Find the degree
sequence of each of the following graphs.
(a). The graph you drew in
exercise 1 for section 9.1 above (emails).
(b). Thepseudograph you drew in exercise 1 for this section (emails).

5. Determine whether the
given graphs below are bipartite. If it is bipartite, exhibit
the bipartition sets. If it is not bipartite,
explain why.

6. Consider the graph you
drew for exercise 1, section 9.1 above (emails). Is this a complete graph? Why
or why not? If not,
explain how you could complete the graph” by adding an edge or edges. Is
this
a bipartite graph? Why or
why not? If not, explain how you could make the graph bipartite” by
removing an edge or edges
(_nd a bipartite subgraph).

7. Use the Handshake
Theorem (Proposition 9.2.5) to solve the following problem. Suppose that you
arrive at a gathering of 8 people. Suppose that upon your arrival, you learn
two facts: that 12 handshakes
have already taken place
and that every person participated in the same number of handshakes,h.
How many hands did each of the 8 people
shake? (Findh).
Section
9.3:

1. Determine which of the
five pairs graphs in this applet exercise are isomorphic and which are not.
If a pair of graphs are
isomorphic to each other, then label the nodes in each graph and exhibit an
isomorphism function (cf.
Fig 9.26, Fig 9.27 and Example 12 in the textbook for ideas on how to do
this; you might also
consider a color-coding scheme as in the example in the content guide for
section
9.3). If a pair of graphs are non{isomorphic,
explain why.
.ship.edu/deensley/DiscreteMath/flash/ch7/sec7_3/isomorphism.html”>http://webspace.ship.edu/deensley/DiscreteMath/flash/ch7/sec7_3/isomorphism.html
2. Give an example of a pair of graphs which
have identical degree sequences, but which are not isomorphic.
Section
13.1:

1. Can five houses be
connected to two utilities without connections crossings? Explain why or why
not.
If the answer is yes, then draw a graph that
shows a possible solution.
2. Determine which of the
five graphs in this applet exercise are planar. If a graph is planar, draw it
so
that no edges cross. If a graph is
non{planar, give a reason why it is non-planar.
.ship.edu/deensley/DiscreteMath/flash/ch7/sec7_3/planargraphs.html”>http://webspace.ship.edu/deensley/DiscreteMath/flash/ch7/sec7_3/planargraphs.html
3.