Homework 1 Math 688 Graduate Combinatorics I
Fall 2020
Due Friday, September 11
1. (2 points) Let I be a connected graph that contains exactly two vertices of odd degrees.
Prove that there exists a walk from one vertex of odd degree to the other vertex of odd
degree that goes through every edge exactly once.