# Math 412 Introduction to Graph Theory Sections X13

Instructor:   Jozsef   Balogh
Office: 233B Illini Hall
Phone: (217) 244-1918 (office)
E-mail: jobal@illinois.edu
Time and place: 12:00 pm- 12:50 pm MWF, 245 Altgeld Hall
Final exam: December 17, Tuesday 8:00- 11:00 am
Office hours: after classes, and 1:00 pm- 1:50 pm Fridays.
Study sessions : 1:00 pm- 2:50 pm Wednesdays, 007 Illini Hall
TEXTBOOK: Introduction to Graph Theory, D. West (Prentice Hall), 2-nd ed., Chapters 1-7.
TEST1 : October 2 Wednesday 6:00pm - 7:30pm, 245 AH
Material to be covered from Sections 1.1 -- 2.2.
TEST2 : November 13 Wednesday 6:00pm - 7:30pm 245 AH Material to be covered from Sections 2.3 -- 5.1.
TEST3 : December 11 Wednesday 6:15pm - 7:45pm 245 AH Material to be covered from Sections 5.1- - 7.2.

In case you cannot attend a TEST, let me know in advance!!!

Classes will be cancelled (because of evening tests): September 6 and 13 and December 11.

HOMEWORK: FALL 2019:

From each homework assignments 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 September 16,    Monday, before class:
Warm up problems:       Section 1.1: 4, 5, 7, 9, 11.                  Section 1.2: 1, 4, 5, 7, 8, 9, 10, 11.
Extra problems:            Section 1.1: 16, 18, 19, 20, 22, 24, 25, 26, 27, 30, 31,36, 37, 38;        Section 1.2: 14, 16, 18, 20, 21, 22, 23, 28, 41.
Homework Problems (to be collected)       Section 1.1: 14, 18, 26, 37;        Section 1.2: 20, 26.

Homework 2 ,    due September 20,     Friday, before class:
Warm up problems:       Section 1.3: 1, 3, 4, 5, 8, 9; .
Extra problems:            Section 1.3: 12, 13, 17, 18, 24, 40, 41, 57, 63;        .
Homework Problems (to be collected)       Section 1.2: 38, 40;        Secti0on 1.3: 18, 40, 47, 52.

Homework 3 ,    due September 27,     Friday, before class:
Warm up problems:       Section 1.4: 3, 4, 5, 7,8 Section 2.1: 2, 3, 4, 5, 6, 7, 8, 13. Section 2.2: 1, 2, 3; .
Extra problems:           Section 1.4: 9, 10, 21, 26, 28, 29, 36, 37. Section 2.1: 15, 19, 27, 29, 30, 31, 44, 52, 53. Section 2.2: 6, 7, 8, 10, 11, 12, 15, 17;
Homework Problems (to be collected)       Section 1.4: 10, 36 Section 2.1: 29, 37, Section 2.2: 8, 15;

Homework 4 ,    due October 11,     Friday, before class:
Warm up problems:       Section 2.3.:1, 2, 3.                  Section 3.1: 1, 2, 3, 5, 6, 7 .
Extra problems:            Section 2.3: 7, 8, 9, 10, 12, 13, 14, 17, 20, 22,        Section 3.1: 8, 9, 18, 19, 20, 21, 22, 24, 26, 28, 31, 34, 29, 40 .
Homework Problems (to be collected)       Section 2.3: 8, 10, 12;        Section 3.1: 26, 31, 32.

Homework 5 ,    due October 21,     Monday, before class:
Warm up problems:       Section 3.3: 1, 2, 4,            Section 4.1: 1, 2, 4.            .
Extra problems: Section 3.3: 6, 7, 8, 10, 11, 13, 14, 15, 16, 17, 18, 19, 20, 22, 24, 25, 26.           Section 4.1: 11, 12, 14, 19, 24, 25, 28.
Homework Problems (to be collected)       Section 3.3: 10, 16, 25.        Section 4.1: 11, 24, 25.

Homework 6 ,    due November 6,     Wednesday, before class:
Warm up problems:       Section 4.2: 1, 7, 8, 9; Section 4.3: 2, 3; Section 5.1: 1, 4, 6, 7, 8, 12, 13, 14, 15;                  .
Extra problems:            Section 4.2: 11, 12, 13, 14, 23, 24; Section 4.3: 5, 6, 7, 8, 10, 13, 14; Section 5.1: 20, 21, 22, 31, 32, 33, 38, 39, 40, 41, 42;        .
Homework Problems (to be collected)       Section 4.2: 11, 23; Section 4.3: Problem 2: change all capacities of 4 to 8; all capacities of 6 to 9; and all capacities of 5 to 10; 6, 10 Section 5.1: 22 .

Homework 7 ,    due November 22,     Friday, before class:
Warm up problems:       Section 5.2: 2;     Section 5.3: 1, 3, 4,     Section 6.1: 1, 3, 4, 7, 8, 9, 10;               .
Extra problems:            Section 5.2: 7, 9, 11, 15, 16, 17, 18, 21 23, 25, 26, 27, 32.     Section 5.3: 6, 7, 8,     Section 6.1: 5, 12, 25, 29, 33;        .
Homework Problems (to be collected)       Section 5.1. 33, 41.     Section 5.2. 9, 11, 15.     Section 6.1: 25.

Homework 8 ,    due December 9,     Monday, before class:, no late homework is accepted.
Warm up problems:       Section 5.2: 2;     Section 6.2: 1, 2 (a), (b), 4, 5, Section 6.3: 3, 4, 5, 16 Section 7.1: 1, 2, 4; Section 7.2: 4. Section 8.3: 2,               .
Extra problems:            Section 6.2: 7, 8, 9, Section 6.3:: 13 Section 7.1: 26, 34. Section 7.2: 6, 17, 25, 29,        .
Homework Problems (to be collected)       Section 5.3: 5 Section 6.1: 26, 34 Section 6.2: 2 (a), (b). Section 7.1: 26, Section 7.2: 25.

HOMEWORK: FALL 2016:

From each homework assignments 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:

•                              DUE:  Due Friday, January 29, 2016: BEFORE CLASS!

•                              DUE:  Due Friday, February 5, 2016: BEFORE CLASS!

•                              DUE:  Due Friday, February 19, 2016: BEFORE CLASS!

•                              DUE:  Due Friday, February 26, 2016: BEFORE CLASS!

•                              DUE:  Due Friday, March 4, 2016: BEFORE CLASS!

•                              DUE:  Due Wednesday, March 16, 2016: BEFORE CLASS!

•                              DUE:  Due Monday, April 4!!, 2016: BEFORE CLASS! Note, typo in problem 1: delta(G)>n/4, not >=!

•                              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!

•                              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)