Lesson plan

Locally linear graph

is locally linear. Its six triangles are visible as equilateral triangles in this layout. In graph theory, a locally linear graph is an undirected graph in which every edge belongs to exactly one triangle. Equivalently, for each vertex of the graph, its neighbors are each adjacent to exactly one other neighbor. That is, locally (from the point of view of any one vertex) the rest of the graph looks like a perfect matching. Locally linear graphs have also been called locally matched graphs. More technically, the triangles of any locally linear graph form the hyperedges of a triangle-free 3-uniform linear hypergraph, and they form the blocks of certain partial Steiner triple systems; and the locally linear graphs are exactly the Gaifman graphs of these hypergraphs or partial Steiner systems. Many constructions for locally linear graphs are known. 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. The question of how many edges locally linear graphs can have is one of the formulations of the Ruzsa–Szemerédi problem.…

Back to article

Article summary

is locally linear. Its six triangles are visible as equilateral triangles in this layout. In graph theory, a locally linear graph is an undirected graph in which every edge belongs to exactly one triangle. Equivalently, for each vertex of the graph, its neighbors are each adjacent to exactly one other neighbor. That is, locally (from the point of view of any one vertex) the rest of the graph looks like a perfect matching. Locally linear graphs have also been called locally matched graphs. More technically, the triangles of any locally linear graph form the hyperedges of a triangle-free 3-uniform linear hypergraph, and they form the blocks of certain partial Steiner triple systems; and the locally linear graphs are exactly the Gaifman graphs of these hypergraphs or partial Steiner systems. Many constructions for locally linear graphs are known. 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. The question of how many edges locally linear graphs can have is one of the formulations of the Ruzsa–Szemerédi problem.…

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.