Planar-graph teaching needs just 2 examples: the old bound was 5, and telling 1 from 2 stays NP-hard

For teaching closed neighborhoods in planar graphs, the non-clashing teaching dimension drops to 2, and to 4 when only positive examples may be used, with both bounds attained. The previously known upper bounds for the same family were 5 and 7, and whether planar closed neighborhoods satisfy the conjectured teaching-dimension-versus-VC-dimension inequality was open. A construction gives size at most 2 for every planar graph, and a planar instance shows the bound cannot be lowered; the positive case likewise gets a size-4 construction and an instance attaining 4.

The construction handles vertices by degree and keeps each concept's teaching set small, then repairs the remaining conflicting pairs. It starts from a preliminary teaching set per vertex and modifies it in four steps covering twin vertices, saturating vertices, and the remaining vertices, while preserving pairs already distinguished. The positive case first bounds outerplanar graphs by 2, then extends to planar graphs with teaching sets of size at most 4; the general case uses that any class of at most five concepts admits a size-one non-clashing map, and that a planar graph with minimum degree at least 5 has a degree-5 vertex whose neighborhood family admits a size-one map.

Deciding whether the non-clashing teaching dimension is at most 1 stays NP-complete for closed neighborhoods of planar graphs, in both the general and positive settings. Even with the upper bound of 2 known for this family, distinguishing the values 1 and 2 remains hard. The reduction starts from Planar-SAT and builds a planar graph with a closed-neighborhood family of polynomial size, covering both the general and positive variants.

The results apply to concept classes of closed neighborhoods in planar graphs, covering both the general and positive-only non-clashing teaching settings, with tight bounds of 2 and 4. The NP-completeness of deciding whether either dimension is at most 1 is likewise confined to this family. The authors propose extending the results to graph classes of linear neighborhood complexity and examining whether similar relations hold between non-clashing teaching and sample compression.

Whether the teaching dimension is always bounded by the VC dimension for every finite concept class remains open; only the planar closed-neighborhood family is settled here. The authors also note that extending to graph classes of linear neighborhood complexity and connecting non-clashing teaching to sample compression are still open directions.