Embedding a finite forest under cardinality and minimum-degree bounds
ProvedArexychen.Erdos180.embedsAsSubgraph_of_isAcyclic_of_card_le_minDegreearexychen-erdos180-migrationerdos-180extremal-graph-theorygraph-theory
Let and be simple graphs on finite vertex types and , respectively, and assume that adjacency in is decidable. If is acyclic and and , then there exists an injective map preserving every edge of . This is ordinary subgraph containment: nonedges need not be preserved. Both cardinality bounds are retained, and the vertex count of includes isolated vertices.
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.DeleteEdges 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 attribute [local instance] SimpleGraph.neighborSetFintype universe u v open Arexychen.Erdos180
Formal statement
theorem Arexychen.Erdos180.embedsAsSubgraph_of_isAcyclic_of_card_le_minDegree
{α : Type u} {β : Type v} [Fintype α] [Fintype β]
(F : SimpleGraph α) (G : SimpleGraph β)
[DecidableRel G.Adj]
(hF : F.IsAcyclic)
(hcard : Fintype.card α ≤ Fintype.card β)
(hdeg : Fintype.card α ≤ G.minDegree) :
EmbedsAsSubgraph F G := by sorry
Source