Задача 3. На схеме показаны уже проложенные каналы связи между пунктами A, B, C, D, E, F. Требуется проложить ровно два новых канала так, чтобы к пунктам A, B, C, D, E, F подходило соответственно 4, 3, 3, 3, 3, 2 канала. Какие каналы необходимо провести? Варианты: AC, AF, BD, BE, CF, DE, DF.

По схеме уже проложены каналы AB, AD, AE, BC, BF и FE.

Сейчас к A подходят 3 канала, к B — 3, к C — 2, к D — 2, к E — 2, к F — 2. Значит, нужно добавить по одному каналу к A, C, D и E; степени B и F менять не требуется.

Из предложенных вариантов каналы AC и DE добавляют ровно по одному соединению нужным пунктам A, C, D и E, не затрагивая B и F.

Ответ: AC и DE.