Ordinary containment bounds the reduced edge count
ProvedArexychen.Erdos180.edgeCount_deleteIsolated_le_of_embedsarexychen-erdos180-migrationerdos-180extremal-graph-theorygraph-theory
Let and be simple graphs on arbitrary vertex types, and assume the edge set of is finite. If admits an injective edge-preserving map into , then the natural-number cardinality of the edge set of the graph obtained from by deleting isolated vertices is at most that of . No finite-vertex assumption is required.
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_deleteIsolated_le_of_embeds
{α : Type u} {β : Type v}
(H : SimpleGraph α) (G : SimpleGraph β)
[Finite G.edgeSet]
(hemb : EmbedsAsSubgraph H G) :
edgeCount (deleteIsolated H) ≤ edgeCount G := by sorry
Source