Content deleted Content added
→Distance=regular graphs: typo |
→Density: minimum density |
||
Line 57:
Among [[planar graph]]s, the maximum number of edges in a locally linear graph with <math>n</math> vertices is <math>\tfrac{12}{5}(n-2)</math>. The graph of the [[cuboctahedron]] is the first in an infinite sequence of [[polyhedral graph]]s with <math>n=5k+2</math> vertices and <math>\tfrac{12}{5}(n-2)=12k</math> edges, for <math>k=2,3,\dots</math>, constructed by expanding the quadrilateral faces of <math>K_{2,k}</math> into antiprisms. These examples show that the <math>\tfrac{12}{5}(n-2)</math> upper bound can be attained.{{r|z}}
Every locally linear graph has the property that it remains connected after any matching is removed from it, because in any path through the graph, each matched edge can be replaced by the other two edges of its triangle. Among the graphs with this property, the least dense are the triangular cactus graphs, which are also the least dense locally linear graphs.{{r|fp}}
==References==
| |||