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 be a graph that has at least 5 vertices. The complement of is a graph on the same vertices such that two vertices of are adjacent if and only if they are not adjacent in *. *Show that or contains a cycle

### Like this:

Like Loading...

Filed under: Uncategorized |

Adam Pietrafesa, on June 20, 2010 at 6:58 pm said:no class on thursday. is this due friday?

cot3100su10, on June 21, 2010 at 10:38 am said:Yes, the due date is Friday, July 2nd.