## Homework 4

Homework 4 is due on Thursday, July 1st.

0. Read Chapter 9. Indicating in at most three sentences one or more of the following: the passage in the reading— including its page number—you:

• Found most difficult
• Found most surprising
• Would like to have discussed in the next lecture

1. Show that Dijkstra’s algorithm may not work if edges can have negative weights

2. Show that for any undirected graph with |V|  >= 2 nodes there exist two vertices with the same degree.

3. Let G be a graph and v a vertex in G with degree  at most half the average degree of the Graph. Show that deleting the vertex v (and all incident edges) does not decrease the average degree of the Graph.

4. Let $G = (V;E)$ be a graph that has at least 5 vertices. The complement of $G$ is a graph $\bar{G} = (V, \bar{E})$  on the same vertices such that two vertices of $\bar{G}$ are adjacent if and only if they are not adjacent in $G$. Show that $G$ or $\bar{G}$ contains a cycle