Surface Embedding of Non-Bipartite $k$-Extendable Graphs

Abstract

For every surface, we find the minimum number $k$ such that every non-bipartite graph that is embeddable in that surface is not $k$-extendable. In particular, we construct a family of $3$-extendable graphs which we call bow-tie graphs. This confirms the existence of an infinite number of $3$-extendable non-bipartite graphs that are  embeddable in the Klein bottle.