Course Description

This course is delivered remotely. Students are expected to be online during the scheduled class and lab (tutorial) times and are expected to log in to UMLearn before classes or labs for advance material, and between class times to keep up with discussions and readings.  Your computer or device, and Internet connection must meet the UM minimum requirements.  Students must have Webex installed. Additional contact, especially individual contact, may also be available by Zoom or similar platforms. All term tests will take place during the scheduled lecture times, and students are expected to be available during the periods in which they are registered.

This course is an introduction to graphs, directed graphs, and multigraphs.  Topics include trees, cycles and circuits, planarity, basic graph algorithms, and applications of graph theory to social and physical sciences. Specifically, the course will cover the following topics from Graph Theory Notes for Undergraduates (not necessarily in the given order):

(1) Graph theory basics: origins of graph theory; basic concepts and definitions; walks, trails, paths, cycles, and circuits; graph isomorphism; standard classes of graphs; new graphs from old, degrees, connected graphs (Chapter 1).

(2) Cycles and circuits: existence of cycles; Eulerian graphs and Euler circuits; Hamilton cycles and paths; the travelling salesperson problem (Chapter 2).

(3) Trees and forests:  basic properties of trees and forests; counting non-isomorphic trees; minimum spanning trees (Chapter 3).

(4) Connectivity and Menger’s theorem: vertex connectivity; edge connectivity (Chapter 4).

(5) Graph colouring: vertex colouring basics; critical graphs; edge colourings; perfect graphs; colouring planar graphs and the four colour theorem (Chapters 6).

(6) Planar graphs: face degrees and platonic solids; archimedean solids; Fary’s Theorem; dual of a planar graph (Chapter 7).

(7) Digraphs and Tournaments: directed graphs; strongly connected digraphs and orientable graphs; Eulerian circuits; tournaments (Chapter 12).

There is a possibility that new heath restrictions will allow us to return to “in-person” classes. If that is the case we will update the syllabus as needed.

Instructor Contact Information

Course Components

Assignments

There will be five (5) assignments throughout the term, each worth 3% of your final grade. The problems will be graded on correctness and clarity; solutions that are difficult to read will not receive many marks.  While it is perfectly acceptable to discuss approaches to the assignment problems, it is expected that students actually solve and present solutions by themselves. Acts of academic dishonesty will be dealt with harshly.

Assignments will be will be emailed to you through Crowdmark one week before they are due. Assignments will be submitted through Crowdmark as well. Assignments that have illegible writing or pages out of order will lose marks. Late assignments will NOT be accepted.

Writing Assignments

There will be five (5) writing assignments throughout the term, each worth 2% of your final grade.  The point of this assignment is for you to practice and receive feedback on your math- ematical writing skills.   The grading will become more strict throughout the term, with the intention that your writing improves.  A document will be posted on UM Learn that contains advice on how to present your solutions.

Each writing assignment consists one (1) question (possibly with multiple parts). You may talk to any of your classmates about how to SOLVE the problem. Additionally, the problem will

be presented with generous hints about how to solve it. However, presentation of your solutions must be entirely your OWN WORK. Late writing assignments will NOT be accepted.

Lab Worksheets

Each worksheet will be posted on UM Learn in advance so that you have an opportunity to attempt the problems before your lab times.  During the lab, the TA will go over some of the problems and answer any questions you may have.  Note that the lab worksheets are NOT for credit; they are meant as extra practice.  Solutions to lab worksheets will not be posted, so it would be beneficial to attend your scheduled lab (NOTE: This may change to in-person if health restrictions allow).

Term Tests

Term tests will take place online via Crowdmark during the regularly scheduled lectures (NOTE: This may change to in-person if health restrictions allow). Each test is worth 15% of your final grade. Students who miss a test for an acceptable reason must contact their individual instructor within 48 hours of the missed test (email is acceptable for this), otherwise they will receive a zero for this component.

It is imperative that you are familiar with uploading your documents to Crowdmark before a test as failure to upload correctly will result in marks being deducted (potentially all of your marks).  An electronic copy of your graded test/exam will be released to you shortly after all tests have been graded.

Final Exam

The final exam will be an individual, online, two hour exam via Crowdmark that covers all topics in the course (NOTE: This may change to in-person if health restrictions allow). The final exam will be worth 30% of your final grade.  An electronic copy of your graded test/exam will be released to you shortly after all exams have been graded and any deferred exams have been written. Final examination and grades policies can be found here:

http://umanitoba.ca/admin/governance/governing_documents/academic/1299.html

For more resources about examinations, see here:

http://umanitoba.ca/faculties/science/undergrad/resources/Academic%20Resources%20index. html

General Faculty of Science policies on viewing final examinations can be found here:

http://umanitoba.ca/faculties/science/undergrad/resources/895.html

Students wishing to appeal their term work grade can do so through the Registrar’s office. A fee is charged for each appeal. More information can be found here:

http://umanitoba.ca/student/records/grades/690.html

Course Evaluation Methods

Your final grade will be based on your performance on the definition quizzes, writing assign- ments, tutorial work, two tests, and the final exam.

There are no deferred assignments, writing assignments, nor term tests. If you miss an assign- ment or writing assignment, you will be assigned a mark of “0” unless acceptable reasons are provided. In this case, the weight of the missed component will be moved to your Final Exam. If you miss a term test, you will be assigned a mark of “0” unless acceptable reasons are provided. In this case, the weight of the missed test will be redistributed between the other two term tests and the Final Exam (20%-20%-35%). If you miss at least two term tests, you will have to write a make-up test. The following are the percentage ranges to achieve each letter grade.

These percentages will not be adjusted upwards.  However, they may be adjusted downwards after the final exam.