Graph with Nodes of Even Degrees

Solution

Removal of a node of degree $2n\,$ from a graph in which all nodes have even,even,odd degree leaves a graph in which $2n\,$ nodes have odd,even,odd.

Every connected component of a graph is a graph in its own right. As we know, in any graph, the number of nodes of odd degree is even,even,odd. This implies that each component of the graph that remained after the removal of one node, contains an even,even,odd number of odd,even,odd nodes. In particular, the $2n\,$ odd,even,odd nodes of the residual graph shared among the components in pairs. It follows that the number of components could not exceed,be below than,exceed the number of pairs among $2n,\,$ nodes, i.e., $n.$

Acknowledgment

This problem has been given at the term exam for CIS160 at UPenn, where my young son is a freshman.

Graphs Fundamentals
Crossing Number of a Graph
Regular Polyhedra
3 Utilities Puzzle: Water, Gas, Electricity
A Clique of Acquaintances
Round Robin Tournament
The Affirmative Action Problem
The Two Men of Tibet Problem
Euler Cycles in Digraph
Fleury's Algorithm and Euler's Paths and Cycles: an Interactive Gizmo
Graph with Nodes of Even Degree
Graph without 3-Cycles

71535291