page_title: Locally linear graph
section_title: Density
hierarchical_section_title: Locally linear graph / Density
context_page_description: In graph theory, a locally linear graph is an undirected graph in which the neighborhood of every vertex is an induced matching. That is, for every vertex, every neighbor of should be adjacent to exactly one other neighbor of. Equivalently, every edge of such a graph belongs to a unique triangle. Locally linear graphs have also been called locally matched graphs.
  Examples of locally linear graphs include the triangular cactus graphs, the line graphs of 3-regular triangle-free graphs, and the Cartesian products of smaller locally linear graphs. Certain Kneser graphs, and certain strongly regular graphs, are also locally linear.
  Some locally linear graphs have a number of edges that is near-quadratic. The question of how dense these graphs can be is one of the formulations of the Ruzsa–Szemerédi problem. The densest planar graphs that can be locally linear are also known.
context_section_description: One formulation of the Ruzsa–Szemerédi problem asks for the maximum number of edges in an -vertex locally linear graph. As Imre Z. Ruzsa and Endre Szemerédi proved, this maximum number is  but is  for every .
  The construction of locally linear graphs from progression-free sets leads to the densest known locally linear graphs, with  edges.
  Among planar graphs, the maximum number of edges in a locally linear graph with  vertices is . The graph of the cuboctahedron is the first in an infinite sequence of polyhedral graphs with  vertices and  edges, for , constructed by expanding the quadrilateral faces of  into antiprisms. These examples show that this upper bound is tight.
caption: The densest possible locally linear planar graphs are formed by gluing an antiprism (red vertices and black edges) into each quadrilateral face of a planar graph (blue vertices and dashed yellow edges)