Graphy Theory Question Prove that it is impossible to have a

Graphy Theory Question

Prove that it is impossible to have a graph in which there are an odd number of odd-degree vertices.

Solution

In general if there are two node at most, then one node used to start walking and the other to end.

A) If we start from odd one, this means we have two scenarios:

1) if odd =1 then we start from it and leave it forever; this means: visiting once (Starting Point).

2)if odd>1 then we have to revisit it again, but we will leave it because # edges will enforce us to leave it at the end.

B) if then having another node with odd degree, this mean we have to stop at it. because entering node with odd edges enforces us to stay on it at the end, being no possibility to go out forever.