The minimum degree of Ramsey‐minimal graphs

We write H  →  G if every 2‐coloring of the edges of graph H contains a monochromatic copy of graph G . A graph H is G ‐ minimal if H  →  G , but for every proper subgraph H ′ of H , H ′ ↛  G . We define s ( G ) to be the minimum s such that there exists a G ‐minimal graph with a vertex of degree s . We prove that s ( K k ) = ( k  − 1) 2 and s ( K a,b ) = 2 min( a,b ) − 1. We also pose several related open problems. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 167–177, 2007