Odd Graphs: What Mathematicians Have to Say

The highlighted part of this graph forms a subgraph in which all the vertices have an odd number of connections with each other. Mathematicians now know the minimum size of a subgraph guaranteed to have this property in any graph.

For decades, mathematicians have debated a simple question about graphs and the number of connections they have. Now, using arguments an undergraduate math student could have come up with, Asaf Ferber of the University of California, Irvine and Michael Krivelevich of Tel Aviv University have finally provided the answer in the form of a proof posted in March.

“It’s a bit of a surprise, at least for me, that such a combination of clever but basic arguments suffice[d],” said Yair Caro, a mathematician at the University of Haifa.

Graphs are collections of vertices (dots) connected by edges (lines). After hundreds of years of study, mathematicians are still investigating their basic properties. One concerns the “parity” of a graph’s vertices, meaning whether they are connected to an odd or even number of other vertices.

Leave a Comment