Graph with Nodes of Even Degrees

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.

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

Copyright © 1966-2016 Alexander Bogomolny

 62018230

Search by google: