Embedding a reduced star while accommodating isolated vertices
ProvedArexychen.Erdos180.embeds_of_deleteIsolated_isStar_of_degree_ge_cardarexychen-erdos180-migrationerdos-180extremal-graph-theorygraph-theory
Let be a graph on a finite vertex type , let be a graph on any vertex type, and let be a vertex of with a finite neighbor set. If deleting isolated vertices from leaves a star and , then the whole graph admits an injective edge-preserving map into . Its isolated vertices are included in the bound .
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.embeds_of_deleteIsolated_isStar_of_degree_ge_card
{α : Type u} {β : Type v} [Fintype α]
(H : SimpleGraph α) (G : SimpleGraph β) (v : β)
[Fintype (G.neighborSet v)]
(hstar : IsStar (deleteIsolated H))
(hdeg : Fintype.card α ≤ G.degree v) :
EmbedsAsSubgraph H G := by sorry
Source