Math 412
Introduction to Graph Theory
Sections X13 and X14
Instructor: Jozsef Balogh
Office: 233B Illini Hall
Phone: (217) 244-1918 (office)
E-mail: jobal@math.uiuc.edu
Time and place: 2:00 pm- 2:50 pm MWF, 245 Altgeld Hall
Final exam: December 13, Tuesday 8:00- 11:00 am
Office hours: after classes 3:00 pm- 3:50 pm MWF and by appointment.
Study sessions : after classes 3:00 pm- 3:50 pm Monday, IH 1.
TEXTBOOK: Introduction to Graph Theory, D. West (Prentice Hall), 2-nd ed., Chapters 1-7.
TEST1 : September 21 Wednesday 6:00pm - 7:30pm, AH 245
TEST2 : October 19 Wednesday 6:00pm - 7:30pm AH 245 Material to be covered from Sections 2.2 - 4.2.
TEST3 : November 16 Wednesday 6:00pm - 7:30pm AH 245 Material to be covered from Sections 4.1, 4.2, 4.3, 5.1, 6.1, 6.2, 6.3;
In case you cannot attend a TEST, let me know in advance!!!
Classes will be cancelled (because of evening tests): November 11, December 2 and 7.
HOMEWORK: FALL 2016:
From each homework assigments solve five out of the six to be collected problems. The solutions should include proofs, should be readable and as self-complete as possible.
Homework 1 , due August 31, Wednesday, before class:
Warm up problems: Section 1.1: 2, 4, 5, 7, 9, 10. Section 1.2: 1, 4, 5, 8, 9, 10, 11.
Extra problems: Section 1.1: 11, 18, 20, 22, 23, 24. Section 1.2: 14, 18, 23, 41.
Homework Problems (to be collected)
Section 1.1: 19, 26, 31, 38; Section 1.2: 20, 28.
Homework 2 , due September 7, Wednesday, before class:
Warm up problems: Section 1.3: 1, 4, 5, 9, 12.
Section 1.2: 1, 4, 5, 8, 9, 10, 11.
Extra problems: Section 1.3: 24, 40, 41, 57, 63.
Homework Problems (to be collected)
Section 1.2: 39, 40; Section 1.3: 12, 18, 41, 54.
Homework 3 , due September 14, Wednesday, before class:
Warm up problems: Section 1.4: 3, 4, 7;
Section 2.1: 2, 3, 4, 5, 6, 7, 13.
Extra problems: Section 1.4: 9, 10,
21, 26, 28, 29, 36, 37.
Section 2.1: 19, 27, 30, 31, 44, 52, 53.
Homework Problems (to be collected)
Section 1.3: 40, 47; Section 2.1: 15, 29, 37, 44.
Homework 4 , due September 28, Wednesday, before class:
Warm up problems: Section 2.2: 1, 2, 3;
Section 2.3: 1, 2, 3.
Extra problems: Section 2.2: 6, 7, 8, 10, 12, 15,;
Section 2.3: 7, 8, 12, 14, 20, 22.
Homework Problems (to be collected)
Section 2.2: 8, 11, 15, 17; Section 2.3: 7, 10.
Homework 5 due October 5, Wednesday, before class:
Warm up problems: Section 3.1: 3, 5, 6, 7;
Section 3.3: 1, 2, 3, 4.
Extra problems: Section 3.1: 8, 9, 18, 20, 22, 24, 26, 29, 31, 34, 39;
Section 3.3: 6, 7, 8, 10, 11, 13, 14, 15, 19, 22, 24, 26.
Homework Problems (to be collected)
Section 3.1: 21, 24, 28, 40; Section 3.3: 8, 16.
Homework 6 due October 12, Wednesday, before class:
Warm up problems: Section 4.1: 10, 12, 18, 31;
Section 4.2: 8, 9, 11, 14, 20, 26;
Extra problems: Section 3.1: 8, 9, 18, 20, 22, 24, 26, 29, 31, 34, 39;
Section 3.3: 6, 7, 8, 10, 11, 13, 14, 15, 19, 22, 24, 26.
Homework Problems (to be collected)
Section 4.1: 14, 19, 24; Section 4.2: 12, 23, 24;
Homework 7 due October 26, Wednesday, before class:
Warm up problems: Section 4.3: 1, 2, 3;
Section 5.1: 1, 4, 7, 8, 12, 14, 15;
Extra problems: Section 4.3: 5, 7, 10, 13;
Section 5.1: 20, 22, 33, 38, 39, 40, 41;
Homework Problems (to be collected)
Section 4.3: Problem 2: change all capacities of 4 to 7; all capacities of 6 to 8; and all capacities of 5 to 9; Problem 10; Section 5.1: 20, 38, 40; Section 5.2: 23;
Homework 8 due December 5 Monday.:
Warm up problems:
Section 6.1: 1, 3, 4, 7, 8, 9, 10; Section 6.3: 1, 2;
Section 7.1: 1, 2, 4; Section 7.2: #3.
Extra problems: Section 6.1: 3, 5, 8, 9, 10, 12, 25, 29, 33; Section 6.2: 1, 4, 5, 8, 9, 11; Section 6.3: 5, 13, 26; nbsp; Section 7.1: 24, 26 nbsp; Section 7.2: 6, 8, 12, 17, 25, 27, 30
Homework Problems (to be collected)
Section 6.1: 26, 30, 34. Section 6.2: 7; Section 7.1: 26, 34.
HOMEWORK: Spring 2016:
- Homework 1:
DUE: Due Friday, January 29, 2016: BEFORE CLASS!
- Homework 2:
DUE: Due Friday, February 5, 2016: BEFORE CLASS!
- Homework 3:
DUE: Due Friday, February 19, 2016: BEFORE CLASS!
- Homework 4:
DUE: Due Friday, February 26, 2016: BEFORE CLASS!
- Homework 5:
DUE: Due Friday, March 4, 2016: BEFORE CLASS!
- Homework 6:
DUE: Due Wednesday, March 16, 2016: BEFORE CLASS!
- Homework 7:
DUE: Due Monday, April 4!!, 2016: BEFORE CLASS!
Note, typo in problem 1: delta(G)>n/4, not >=!
-
Homework 8:
DUE: The first 3 problems are due Friday, April 8!!, 2016: BEFORE CLASS!
Two out of the second 3 problems are due Friday, April 15!!, 2016: BEFORE CLASS!
-
Homework 9:
DUE: due Friday, April 29!!, 2016: BEFORE CLASS!
THIS ASSIGMENTS ARE FROM THE PAST:
- Homework 1:
TBC (To Be Collected): 1.1: 19, 25, 37;
1.2: 22, 29, 33;
DUE: January
28 (Monday)
Recommended: 1.1: 2, 4, 5, 9, 10, 18, 19, 24, 30, 38; 1.2: 1, 4, 8, 11,
14, 15, 20, 22, 23, 28, 30;
- Homework 2: TBC:
1.2: 16, 18; 1.3: 18, 25, 42, 51;
DUE: February
2 (Friday) &nbs;
Recommended: 1.3: 1, 2, 4, 5, 8, 12, 26; 28, 40, 49, 59, 64; 1.4: 3, 4, 5, 7, 10,
11, 13, 27, 37;
- Homework 3: 1.3:. 40, 47, 63; 1.4: 22, 37
2.1. 33;
Recommended: 2.1: 15, 16, 18, 29,
44, 47, 49, 51; 2.2: 1, 2, 3, 5, 6,
7; 2.3: 1, 2, 3, 4, 14,
22; DUE: February 9 (Friday)
-
Homework 4: 2.2: 7, 8,
2.3: 7, 23 , 3.1: 28, 34
Recommended: 3.1: 1, 2, 3, 4, 5,
6, 10, 18, 20, 22,
24, 34, 39; 3.2: 1
DUE: February
23 (Friday)
- Homework 5: 3.1: 18, 26, 31, 40;
3.3: 10, 15;
Recommended: 3.3 1, 2, 3, 5, 10, 11,
15, 22, 26;
DUE: March
2 (Friday)
- Homework 6: 3.3: 6, 14, 16, 25
4.1: 25, 28;
Recommended: 4.1: 1, 2, 6, 8, 10, 14, 28, 31;
DUE: March
9 (Friday)
- Homework 7: 4.2: 31;
4.3: 3, 14;
5.1: 22, 29, 41
Recommended: 4.2:
1, 6, 13, 20, 23, 35; 4.3:
1, 2, 3, 6, 8, 10, 14; 5.1: 1-5, 7, 13, 14,
15, 23, 27, 33, 40;
DUE: March
26 (Monday)
- Homework 8: 5.1: 33; 48
5.2:: 9, 15; 21
5.3: 5
Recommended: 5.1: 1, 2, 3, 4, 5, 7, 13, 14; 15, 23, 27, 33, 40;
5.2: 1, 7, 17;
DUE: April 4
(Wednesday)
- Homework 9:
6.1: 25, 26, 30, 31, 34
6.2:: 7
:
Recommended: 6.1:
3, 5, 8, 9, 10, , 12, 25,
29, 33; 6.2:
;1, 4, 5, 8, 9, 11; 6.3:
5, 13, 15, 19, 26;
DUE: April 16
(Monday)
- Homework 10:
7.1: 24, 26
7.2:: 6, 17, 25, 30
:
Recommended:DUE: April 27
(Friday)