Assignment Week 7  Graphs and Combinatorics
Please submit using the Fire system
Assignments
(1.) Given an undirected graph G where every node has a degree ("gradtal") of 2 or more. Show that G cannot be a tree.
Hint 1: Draw some example graphs where every node has degree >= 2 and try to make them look like trees. You will find this is impossible because you will need to draw too many edges. Think about this: What is the minimum number of edges you need to draw for a graph with n nodes in order to make the degree of every node at least 2?
Hint 2: You may use any lemma ("sats") about graphs in the book. Specifically, lemma 7.3 (page 189) and its proof are relevant, and also lemma 7.7 (page 194).

(2.) Take a look at the directed graph below. How many topological orderings are there for this graph? Motivate your answer.

(3.) How many different strings can you form using exactly the 8 letters A, N, A, C, O, N, D, A in any order?
Compute your answer in two different ways: (1) Write a program that enumerates all possibilities, and (2) Show how the answer can be calculated using formulas from combinatorics.
Ideally, you should get the same answer :)
Hint: If you write your program in Haskell, use the standard Haskell functions nub and permutations from the module Data.List. Don't forget to import Data.List.

Submission
Submission of this assignment should be done electronically through the Fire system.
The submission deadline is Wednesday, October 21, at 13:00. At this time, you should have submitted a serious attempt to solve the assignment. A serious attempt is either an answer you believe to be correct, or a partial answer plus a detailed explanation of what you have tried to come up with a full answer. An empty document is not a serious attempt.
After submitting, you have until Friday October 30 (midnight, OBS: Friday!) to submit a completely correct version.
You can submit your answers in any of the following formats:
If you submit multiple files, please name and/or number them such that the order in which we should read them is obvious. You can also write a text file, and have it refer to pictures that you upload separately.
