Counting edges after deleting one vertex
ProvedArexychen.Erdos180.edgeCount_induce_compl_singletonarexychen-erdos180-migrationerdos-180extremal-graph-theorygraph-theory
For a simple graph on a finite vertex type with decidable adjacency, and any vertex , the induced graph on the complement of satisfies
Here is the natural-number cardinality of the unordered edge set.
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.edgeCount_induce_compl_singleton
{α : Type u} [Fintype α] (G : SimpleGraph α) [DecidableRel G.Adj]
(v : α) :
edgeCount (G.induce ({v}ᶜ : Set α)) + G.degree v = edgeCount G := by sorry
Source