# Discrete Structures - Math 447 - TR 2:00-3:15  Fall 2000

### Professor: Nancy Eaton  Office: Tyler 222  phone: 874-4439 (O), Office Hours: Tues. 3:30, Wed. 2:00, Thurs. 1:00 eaton@math.uri.edu

1 Text

We will use Pearls in Graph Theory by Hartsfield and Ringel as a text for this course. I hope you find this to be a fine book with many examples and exercises.

2 Course Content

A combinatorial graph G = (V,E) is a set of vertices V and edges E, each edge consisting of unordered pairs of vertices. We picture graphs with dots for vertices in any desired arrangement and lines for edges, connected pairs of vertices in that edge. Graph theory has many applications in Electrical Engineering and Computer Science. For example, the electrical engineer will be interested in planar graphs and the computer scientist in algorithms to properly color graphs. We will see some of these applications, but we must build up some background knowledge about graphs before we can make sense of such things as the rigidity of a graph or the crossing number of a graph.

In the course of our study of Graph Theory, we will learn about the following topics as well: set theory, proof techniques, enumeration, and recursive formulas. There is no official prerequisite for this course however, it is recommended that you have been exposed to a variety of math and science courses. All topics will be treated in an introductory manner.

3 Tests

Tests will draw from material covered in class, that is, any theorems, proofs, example, or homework problem that we actually discuss in class is possible material for the tests. So, the best way to prepare for the tests will be to start with your class notes. Notice that implied in the last sentence is that you should take notes! There will be 2 hour exams and a final. The hour exams will be given on October 26 and November 28 and the final will be on December 14 from 3-6 PM.

4 Homework and Office Hours

You learn more by doing, than by watching others give demonstrations. Therefore, homework is very important. When you sit down to do your homework is when you realize whether or not you understood the material from class. You also learn by practice, so do as many of the examples assigned as possible. Homework will be assigned each time we begin to cover a new section in class. You should complete it by the next class period. I will ask you to hand in selected problems every week or so. These should be written up with your best effort at explanation and should be neat. These problems will challenge your problem solving abilities. You may work in groups provided you follow the following guidelines. Each person must write up each problem in their own words, no copying. Whenever you would like to discuss the class material, have any questions or are stuck on the homework, please visit me in my office either during my office hours or by appointment.

 homework 25% 2 tests 40% final 35%

6 Sections covered and Homework

Do the following homework from each section as we cover the section. Each week, I will select problems for you to hand in the following week.

* - Extra credit:  Is the graph in figure 2.2.2 on page 32 really a snark.  Back up you answer.

 SECTION HOMEWORK HAND IN due date 1.1 1-5,8-11 3,11  Sept 14 1.2 1-5,7-10 1,4,9  Sept 28 1.3 1,2,4,7,8,9,13,15,19,20 7,15,19,20  Oct 5 2.1 1,2,4,5,6,7,9,10,11,23 9,10,23  (1 extra credit problem*) Oct 12 2.2 1-3,6,7,9-12 6,10  Oct 17 2.3 1,5-9,13,15,17-19,21,22 work on in class 2.4 2,3,10,11,15,24(as modified in class) 3,10,24 Oct 23 EXAM 1 Oct 26 Research Assignment Nov 2  (latest Nov 21) 3.1 1,3,5,6,11,14,16 6,11,16 Nov 9 Algorithm Nov 9 3.2 1,2,3,6 1,2,3,6 Nov 21 3.3 3,4,6,10,13,14,17 work on in class 4.1 1-5 on board Nov 21 EXAM 2 Nov 28 4.2 2,3,4,6 on board Nov 30 4.3 1,2,3,5 1,2,3,5 Nov 30 5.1 1-7 on board Dec 5 8.1 5,6,8,11 Hand in Dec 7 8.3 2,3 Hand in Dec 7 7.1 7.2 7.3

7 Suggestions

1. Read the Book carefully. I chose this book because I believe it gives nice explanations of things. It may be helpful to read sections before we talk about them in class.
2. Do all of the homework assigned. You should spend an average of 6 hours a week on homework for this class. If you don't gain experience in doing the problems yourself, it will be hard to remember how to do them on a test. It is helpful to start study groups and work together on homework. I do believe that how well you do in this course will depend on how well you study.
3. Attend class to keep current, ask questions, and learn knew topics. Also, attending class allows you to see what is emphasized. Remember the material for the tests will come from what was emphasized.
4. Be sure to keep current of all topics. You will need to study a little almost everyday. If you don't understand something, don't let it wait too long because the concepts in this class build, one upon the next. You don't want the ``snowball effect'' to take over.
5. You may not understand an idea at first. Give it time to sink in. Sometimes you must go over it several times before it begins to make sense. It is not unusual for someone to be stuck on a particular kind of problem and not understand it in class. You may need to have it explained again, later. Please feel free to ask me to do so outside of class.
6. Notecards - I suggest you buy a spiral bound set of notecards. I will explain how to use these in class, but basically, you record simple statements, one per card, giving key definitions and theorems. Then you can use these as a flashcard type of studying method.

7.

File translated from TEX by TTH, version 1.57.