# 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

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1966-2016 Alexander Bogomolny

63431575 |