Degree for non-simple graphs

In class we defined the degree $d(v)$ of a vertex $v$ as the number of vertices adjacent to $v$, but we stressed that this definition was good only for simple graphs. Explain why the definition of $d(v)$ given in class doesn’t satisfy Euler’s handshaking lemma if the graph $\Gamma$ has multiple edges or loops. Can you give a different definition of $d(v)$ that does work?

Chemistry questions

Caffeine has chemical formula $C_8H_{10}N_4O_2$. How many covalent bonds does a molecule of caffeine have?

Explain why, under the basic rules of chemistry, you could not have a molecule with chemical formula $C_9H_{10}N_5O_4$.

Degree Sequences

For each of the following, either give an example of such a graph or prove that no such graphs exist:

• a graph with six vertices whose degrees are 5, 5, 4, 3, 2, 2
• a graph with six vertices whose degrees are 5, 5, 4, 3, 3, 2
• a simple graph with six vertices whose degrees are 5, 5, 5, 5, 3, 3
• a graph with six vertices whose degrees are 5, 5, 5, 5, 3, 3 (will need the first question)

Pigeon Party

Prove that a party, there are two people that know the same number of people. (Note: You need at least two people to have a party. Obviously. Use the pigeon hole principle)

Instant Insanity

Solve the instant insanity puzzle. Copies of the cubes you can cut out are available here:

Isomorphisms

Determine which of the following graphs are isomorphic to one another: