2

For a graph to be factorizable, it seems it has to be of even degree. Could anyone give a simple proof thereof?

Thanks in advance.

Javier Arias
  • 2,033
  • even degree? What is the degree of a graph? Perhaps you meant odd order? As in an odd number of vertices? – Asinomás May 17 '15 at 17:38

1 Answers1

1

A graph $G$ that is factorizable ($1$-factorizable) must have an even number of vertices. This is because for it to be factorizable, in particular it must contain at least one factor ($1$-factor, also known as matching). So it must contain a generating subgraph that is regular of degree $1$. If $G$ had an odd number of vertices this would be impossible because the generating $1$-regular subgraph would have an odd number of vertices of odd degree.

This is impossible, every graph has an even number of vertices of odd degree. As is explained HERE.

Community
  • 1
Asinomás
  • 105,651