A constant edge bound from excluding a star and a matching
ProvedArexychen.Erdos180.edgeCount_le_of_star_free_of_matching_freearexychen-erdos180-migrationerdos-180extremal-graph-theorygraph-theory
Let be natural numbers with and . If a simple graph on has decidable adjacency and contains neither the star nor the -edge matching as an ordinary subgraph, then
This is the existing vertex-cover bound used in the forest/linear classification related to Erdős Problem #180; no optimality or mathematical novelty is claimed.
Preamble
import Definitions.Def_arexychen_erdos180_core import Mathlib.Analysis.Asymptotics.Theta import Mathlib.Combinatorics.SimpleGraph.Acyclic import Mathlib.Combinatorics.SimpleGraph.Basic import Mathlib.Combinatorics.SimpleGraph.Finite import Mathlib.Combinatorics.SimpleGraph.Maps import Mathlib.Combinatorics.SimpleGraph.Matching import Mathlib.Combinatorics.SimpleGraph.Subgraph import Mathlib.Tactic open Filter open Asymptotics universe u v w open Arexychen.Erdos180
Formal statement
theorem Arexychen.Erdos180.edgeCount_le_of_star_free_of_matching_free
{n a b : ℕ} (ha : 2 ≤ a) (hb : 2 ≤ b)
(G : SimpleGraph (Fin n)) [DecidableRel G.Adj]
(hstar : IsHFree (starGraph (0 : Fin (a + 1))) G)
(hmatch : IsHFree (matchingGraph b) G) :
edgeCount G ≤ 2 * (a - 1) * (b - 1) := by sorry
Source