This assignment is due Friday, December 10 at 3pm on paper in AC312. (Note unusual time; I want to get these graded ASAP and may have to leave campus early....) Electronic submissions are welcome as a supplement.

### Graph Facts

For all of the problems in this section, you need consider only simple graphs, i.e., no self-edges and no duplicate edges. The graphs are also all 'connected' - ie, every node has an edge to at least one other node.

- A complete graph is one in which every node has an edge to every other node.
How many edges are in a complete (fully connected)

*undirected*graph with*n*vertices?How many edges are in a complete

*directed*graph with*n*vertices?

- Two graphs are distinct if there's no relabeling of node names that makes them the same.
- How many distinct undirected graphs with four vertices exist?
- How many distinct directed graphs with three vertices exist?

- The degree of a vertex is the number of its neighbors. An undirected graph is a tree if (a) every vertex is connected to every other vertex either directly or indirectly and (b) it contains no cycles, i.e., loops. Note that, by this definition, a tree need not be binary. Find all trees that contain
- that contain no vertices of degree one
- that contain exactly one vertex of degree one
- that contain exactly two vertices of degree one
- that contain exactly three vertices of degree one.

### Graph Algorithms

- Consider the following directed graph:
V = {A, B, C, D, E, F, S} E = {(S, A, 7), (S, B, 3), (S, C, 5) (A, D, 5) (B, A, 5), (B, C, 1), (B, E, 1) (C, B, 2), (E, A, 2), (F, E, 8)}

Dijkstra's algorithm is described in all algorithms textbooks (including Cormen p. 595, with Relax on p. 586) and also at Wikipedia, among other places.

### NP

- Suppose that someone gives you a polynomial-time algorithm to decide formula satisfiability (i.e., given a propositional logic formula, is there some truth assignment that makes it true or does no such truth assignment exist?). Describe how to use this algorithm to find satisyfing assignments -- i.e., to identify one such truth assignment -- in polynomial time.
What you are given is a procedure -- say,

`IsSatisfiable`-- that takes a boolean formula as an argument and returns either yes (if the argument formula is satisfiable) or no (if it is not).`IsSatisfiable`does not take truth assignments along with its formula or return truth assignments. For example:IsSatisfiable( p ^ not( p ) )

IsSatisfiable( (p v q) ^ (not(q) v r) ^ (p ^ not(r)) )

would return true, because both the truth assignment

`{(p, true), (q, false), (r, true)}`and the truth assignment`{(p, true), (q, false), (r, false)}`make`(p v q) ^ (not(q) v r) ^ (p ^ not(r))`true. However,`IsSatisfiable`doesn't produce`{(p, true), (q, false), (r, true)}`or`{(p, true), (q, false), (r, false)}`; it just answers yes.Your task is to come up with a way to find satisfying truth assignments. Like

`IsSatisfiable`, your procedure should take a boolean formula as an argument. Unlike`IsSatisfiable`, your procedure will return a truth assignment. Because your method needs to run in polynomial time, you will need to make use of the magic`IsSatisfiable`polynomial-time decision procedure. Your method may call`IsSatisfiable`on any boolean formula you want. You may call`IsSatisfiable more than once. You may, however, only call it a polynomial number of times. (Calling it an exponential number of times would make your procedure exponential even if`IsSatisfiable` works its magic in polynomial time.)Your answer should consist of a pseudocode algorithm (which is allowed to call

`IsSatisfiable(`*boolean_formula*`)`up to a polynomial number of times) as well as an informal English argument that this algorithm runs in polynomial time (assuming that`IsSatisfiable`does).