AbstractIn [G. Gunther, Neighbor‐connectivity in regular graphs. Discrete Appl. Math. 11 (1985) 233–243] Gunther introduced the concept of a k neighbor‐connected graph, which has the property that the removal of any k − 1 closed neighborhoods neither disconnects the graph, nor leaves only a complete graph. In this paper we pursue the investigation of minimal graphs that are k‐regular in addition to being k neighbor‐connected. In a private communication, Gunther conjectured that if G is such a graph which contains no cliques of size larger than m, then |V(G)| ≧ k2 + (k + 1 − m) (k − 1) + 1. In the above reference, he proved that this conjecture is valid in the case that m = k and characterized the minimal graphs. In this paper, we begin to investigate the case where m = 2. We give some results connecting the minimal graphs to other combinatorial objects.