אינדקס הצביעה של גרף לא מכוון $G = (V, E)$ הוא המספר הקטן ביותר של צבעים הדרוש לצביעת כל קשתות $G$ כך שכל זוג קשתות בעלות צומת קצה משותף צבועות בצבעים שונים.

הוכיחו/הפריכו כל אחת מהטענות הבאות:

א. האלגוריתם החמדן הבא מוצא שידוך מקסימום בגרף דו צדדי: בוחרים קשת, מסירים את קצותיה (כולל הקשתות הנוגעות) מהגרף, חוזרים על הפעולה כל עוד נותרו קשתות.

ב. האלגוריתם החמדן הבא מחשב את אינדקס הצביעה של גרף דו צדדי: מוצאים שידוך מקסימום, מסירים את הקשתות בשידוך, חוזרים על הפעולה כל עוד יש קשתות. אינדקס הצביעה הוא מספר השידוכים שנמצאו.