Scribd
Upload
3 views1 page

Homework 1

Homework 1 is due on February 4, 2026, and requires completion of specific problems from Chapters 1 and 10 of the textbook. Problem 1.10 involves providing an optimal graph coloring, while problem 1.17(a) suggests a proof by contradiction approach. Students are advised to leave space for drawing and grading comments.

Uploaded by

hanxiangli666
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views1 page

Homework 1

Homework 1 is due on February 4, 2026, and requires completion of specific problems from Chapters 1 and 10 of the textbook. Problem 1.10 involves providing an optimal graph coloring, while problem 1.17(a) suggests a proof by contradiction approach. Students are advised to leave space for drawing and grading comments.

Uploaded by

hanxiangli666
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Homework 1 - Due Wednesday, February 4, 2026

Please complete the following problems in our textbook.

Chapter 1, 1.3, 1.10, 1.11, 1.12, 1.17, 1.20(a)

Chapter 10, 10.1

For 1.10, also give this graph an optimal coloring.

In general, please leave yourself enough space to draw a clear graph, as well as enough space
for me to make comments when grading.

Hint for 1.10: Example 10.6 in our book gives a coloring for the traffic lane graph we saw
in class. A key observation is that L2 , L4 , L6 , L8 are all connected, so clearly four colors are
needed to color the subgraph induced by E = {L2 , L4 , L6 , L8 }.
In this problem, I ask for an optimal coloring, meaning that it uses the fewest possible
number of colors, i.e., χ(G).

Hint for 1.17(a): Start by setting up a proof by contradiction.


Assume that P = (u0 , u1 , . . . , un ) and Q = (v0 , v1 , . . . , vn ) are two longest paths of length
n, with all of the ui ’s and vj ’s distinct. Try to prove that there exists another path of length
≥ (n + 1), which would give a contradiction. Therefore, your assumption was wrong that
the vertices are all distinct, and P and Q have at least one vertex in common.

You might also like