A new proof of Delahan's induced-universality result
arXiv:2603.08106v114.1
Predicted impact top 73% in DM · last 90 daysOriginality Synthesis-oriented
AI Analysis
This work offers an alternative proof for a known result in graph theory, primarily benefiting researchers in theoretical computer science and discrete mathematics.
This paper provides a new, concise, and self-contained proof of Delahan's theorem, which states that any simple graph with 'n' vertices can be found as an induced subgraph within a Steinhaus graph containing 'n(n-1)/2 + 1' vertices.
We give a short and self-contained proof of Delahan's theorem stating that every simple graph on $n$ vertices occurs as an induced subgraph of a Steinhaus graph on $\frac{n(n-1)}{2}+1$ vertices. This new proof is obtained by considering the notion of generating index sets for Steinhaus triangles.