[GOAL]
V : Type u
inst✝ : Fintype V
⊢ Fintype (SimpleGraph V)
[PROOFSTEP]
classical exact Fintype.ofInjective SimpleGraph.Adj SimpleGraph.ext
[GOAL]
V : Type u
inst✝ : Fintype V
⊢ Fintype (SimpleGraph V)
[PROOFSTEP]
exact Fintype.ofInjective SimpleGraph.Adj SimpleGraph.ext
[GOAL]
V : Type u_1
W : Type u_2
⊢ Symmetric fun v w => Sum.isLeft v = true ∧ Sum.isRight w = true ∨ Sum.isRight v = true ∧ Sum.isLeft w = true
[PROOFSTEP]
intro v w
[GOAL]
V : Type u_1
W : Type u_2
v w : V ⊕ W
⊢ (fun v w => Sum.isLeft v = true ∧ Sum.isRight w = true ∨ Sum.isRight v = true ∧ Sum.isLeft w = true) v w →
    (fun v w => Sum.isLeft v = true ∧ Sum.isRight w = true ∨ Sum.isRight v = true ∧ Sum.isLeft w = true) w v
[PROOFSTEP]
cases v
[GOAL]
case inl
V : Type u_1
W : Type u_2
w : V ⊕ W
val✝ : V
⊢ (fun v w => Sum.isLeft v = true ∧ Sum.isRight w = true ∨ Sum.isRight v = true ∧ Sum.isLeft w = true) (Sum.inl val✝)
      w →
    (fun v w => Sum.isLeft v = true ∧ Sum.isRight w = true ∨ Sum.isRight v = true ∧ Sum.isLeft w = true) w
      (Sum.inl val✝)
[PROOFSTEP]
cases w
[GOAL]
case inr
V : Type u_1
W : Type u_2
w : V ⊕ W
val✝ : W
⊢ (fun v w => Sum.isLeft v = true ∧ Sum.isRight w = true ∨ Sum.isRight v = true ∧ Sum.isLeft w = true) (Sum.inr val✝)
      w →
    (fun v w => Sum.isLeft v = true ∧ Sum.isRight w = true ∨ Sum.isRight v = true ∧ Sum.isLeft w = true) w
      (Sum.inr val✝)
[PROOFSTEP]
cases w
[GOAL]
case inl.inl
V : Type u_1
W : Type u_2
val✝¹ val✝ : V
⊢ (fun v w => Sum.isLeft v = true ∧ Sum.isRight w = true ∨ Sum.isRight v = true ∧ Sum.isLeft w = true) (Sum.inl val✝¹)
      (Sum.inl val✝) →
    (fun v w => Sum.isLeft v = true ∧ Sum.isRight w = true ∨ Sum.isRight v = true ∧ Sum.isLeft w = true) (Sum.inl val✝)
      (Sum.inl val✝¹)
[PROOFSTEP]
simp
[GOAL]
case inl.inr
V : Type u_1
W : Type u_2
val✝¹ : V
val✝ : W
⊢ (fun v w => Sum.isLeft v = true ∧ Sum.isRight w = true ∨ Sum.isRight v = true ∧ Sum.isLeft w = true) (Sum.inl val✝¹)
      (Sum.inr val✝) →
    (fun v w => Sum.isLeft v = true ∧ Sum.isRight w = true ∨ Sum.isRight v = true ∧ Sum.isLeft w = true) (Sum.inr val✝)
      (Sum.inl val✝¹)
[PROOFSTEP]
simp
[GOAL]
case inr.inl
V : Type u_1
W : Type u_2
val✝¹ : W
val✝ : V
⊢ (fun v w => Sum.isLeft v = true ∧ Sum.isRight w = true ∨ Sum.isRight v = true ∧ Sum.isLeft w = true) (Sum.inr val✝¹)
      (Sum.inl val✝) →
    (fun v w => Sum.isLeft v = true ∧ Sum.isRight w = true ∨ Sum.isRight v = true ∧ Sum.isLeft w = true) (Sum.inl val✝)
      (Sum.inr val✝¹)
[PROOFSTEP]
simp
[GOAL]
case inr.inr
V : Type u_1
W : Type u_2
val✝¹ val✝ : W
⊢ (fun v w => Sum.isLeft v = true ∧ Sum.isRight w = true ∨ Sum.isRight v = true ∧ Sum.isLeft w = true) (Sum.inr val✝¹)
      (Sum.inr val✝) →
    (fun v w => Sum.isLeft v = true ∧ Sum.isRight w = true ∨ Sum.isRight v = true ∧ Sum.isLeft w = true) (Sum.inr val✝)
      (Sum.inr val✝¹)
[PROOFSTEP]
simp
[GOAL]
V : Type u_1
W : Type u_2
⊢ Irreflexive fun v w => Sum.isLeft v = true ∧ Sum.isRight w = true ∨ Sum.isRight v = true ∧ Sum.isLeft w = true
[PROOFSTEP]
intro v
[GOAL]
V : Type u_1
W : Type u_2
v : V ⊕ W
⊢ ¬(fun v w => Sum.isLeft v = true ∧ Sum.isRight w = true ∨ Sum.isRight v = true ∧ Sum.isLeft w = true) v v
[PROOFSTEP]
cases v
[GOAL]
case inl
V : Type u_1
W : Type u_2
val✝ : V
⊢ ¬(fun v w => Sum.isLeft v = true ∧ Sum.isRight w = true ∨ Sum.isRight v = true ∧ Sum.isLeft w = true) (Sum.inl val✝)
      (Sum.inl val✝)
[PROOFSTEP]
simp
[GOAL]
case inr
V : Type u_1
W : Type u_2
val✝ : W
⊢ ¬(fun v w => Sum.isLeft v = true ∧ Sum.isRight w = true ∨ Sum.isRight v = true ∧ Sum.isLeft w = true) (Sum.inr val✝)
      (Sum.inr val✝)
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
h : Adj G a b
⊢ a ≠ b
[PROOFSTEP]
rintro rfl
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a c u v w : V
e : Sym2 V
h : Adj G a a
⊢ False
[PROOFSTEP]
exact G.irrefl h
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
x y : SimpleGraph V
v w : V
h : (x.Adj ⊔ y.Adj) v w
⊢ (x.Adj ⊔ y.Adj) w v
[PROOFSTEP]
rwa [Pi.sup_apply, Pi.sup_apply, x.adj_comm, y.adj_comm]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
x y : SimpleGraph V
v w : V
h : (x.Adj ⊓ y.Adj) v w
⊢ (x.Adj ⊓ y.Adj) w v
[PROOFSTEP]
rwa [Pi.inf_apply, Pi.inf_apply, x.adj_comm, y.adj_comm]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
G : SimpleGraph V
v w : V
x✝ : (fun v w => v ≠ w ∧ ¬Adj G v w) v w
hne : v ≠ w
right✝ : ¬Adj G v w
⊢ ¬Adj G w v
[PROOFSTEP]
rwa [adj_comm]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
x y : SimpleGraph V
v w : V
h : (x.Adj \ y.Adj) v w
⊢ (x.Adj \ y.Adj) w v
[PROOFSTEP]
change x.Adj w v ∧ ¬y.Adj w v
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
x y : SimpleGraph V
v w : V
h : (x.Adj \ y.Adj) v w
⊢ Adj x w v ∧ ¬Adj y w v
[PROOFSTEP]
rwa [x.adj_comm, y.adj_comm]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
s : Set (SimpleGraph V)
⊢ Irreflexive fun a b => ∃ G, G ∈ s ∧ Adj G a b
[PROOFSTEP]
rintro a ⟨G, _, ha⟩
[GOAL]
case intro.intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a✝ b c u v w : V
e : Sym2 V
s : Set (SimpleGraph V)
a : V
G : SimpleGraph V
left✝ : G ∈ s
ha : Adj G a a
⊢ False
[PROOFSTEP]
exact ha.ne rfl
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
f : ι → SimpleGraph V
⊢ Adj (⨆ (i : ι), f i) a b ↔ ∃ i, Adj (f i) a b
[PROOFSTEP]
simp [iSup]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
f : ι → SimpleGraph V
⊢ Adj (⨅ (i : ι), f i) a b ↔ (∀ (i : ι), Adj (f i) a b) ∧ a ≠ b
[PROOFSTEP]
simp [iInf]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
s : Set (SimpleGraph V)
hs : Set.Nonempty s
⊢ (∀ (G : SimpleGraph V), G ∈ s → Adj G a b) → a ≠ b
[PROOFSTEP]
obtain ⟨G, hG⟩ := hs
[GOAL]
case intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
s : Set (SimpleGraph V)
G : SimpleGraph V
hG : G ∈ s
⊢ (∀ (G : SimpleGraph V), G ∈ s → Adj G a b) → a ≠ b
[PROOFSTEP]
exact fun h => (h _ hG).ne
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝ : Nonempty ι
f : ι → SimpleGraph V
⊢ Adj (⨅ (i : ι), f i) a b ↔ ∀ (i : ι), Adj (f i) a b
[PROOFSTEP]
rw [iInf, sInf_adj_of_nonempty (Set.range_nonempty _), Set.forall_range_iff]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a✝ b✝ c u v w : V
e : Sym2 V
src✝ : DistribLattice (SimpleGraph V) := distribLattice
s : Set (SimpleGraph V)
G : SimpleGraph V
hG : ∀ (b : SimpleGraph V), b ∈ s → b ≤ G
a b : V
⊢ Adj (sSup s) a b → Adj G a b
[PROOFSTEP]
rintro ⟨H, hH, hab⟩
[GOAL]
case intro.intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a✝ b✝ c u v w : V
e : Sym2 V
src✝ : DistribLattice (SimpleGraph V) := distribLattice
s : Set (SimpleGraph V)
G : SimpleGraph V
hG : ∀ (b : SimpleGraph V), b ∈ s → b ≤ G
a b : V
H : SimpleGraph V
hH : H ∈ s
hab : Adj H a b
⊢ Adj G a b
[PROOFSTEP]
exact hG _ hH hab
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
src✝ : DistribLattice (SimpleGraph V) := distribLattice
ι✝ : Type u
κ✝ : ι✝ → Type u
f : (a : ι✝) → κ✝ a → SimpleGraph V
⊢ ⨅ (a : ι✝), ⨆ (b : κ✝ a), f a b = ⨆ (g : (a : ι✝) → κ✝ a), ⨅ (a : ι✝), f a (g a)
[PROOFSTEP]
ext
[GOAL]
case Adj.h.h.a
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
src✝ : DistribLattice (SimpleGraph V) := distribLattice
ι✝ : Type u
κ✝ : ι✝ → Type u
f : (a : ι✝) → κ✝ a → SimpleGraph V
x✝¹ x✝ : V
⊢ Adj (⨅ (a : ι✝), ⨆ (b : κ✝ a), f a b) x✝¹ x✝ ↔ Adj (⨆ (g : (a : ι✝) → κ✝ a), ⨅ (a : ι✝), f a (g a)) x✝¹ x✝
[PROOFSTEP]
simp [Classical.skolem]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
src✝ : DistribLattice (SimpleGraph V) := distribLattice
G : SimpleGraph V
v w : V
hvw : Adj ⊤ v w
⊢ Adj (G ⊔ Gᶜ) v w
[PROOFSTEP]
by_cases G.Adj v w
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
src✝ : DistribLattice (SimpleGraph V) := distribLattice
G : SimpleGraph V
v w : V
hvw : Adj ⊤ v w
⊢ Adj (G ⊔ Gᶜ) v w
[PROOFSTEP]
by_cases G.Adj v w
[GOAL]
case pos
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
src✝ : DistribLattice (SimpleGraph V) := distribLattice
G : SimpleGraph V
v w : V
hvw : Adj ⊤ v w
h : Adj G v w
⊢ Adj (G ⊔ Gᶜ) v w
[PROOFSTEP]
exact Or.inl h
[GOAL]
case neg
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
src✝ : DistribLattice (SimpleGraph V) := distribLattice
G : SimpleGraph V
v w : V
hvw : Adj ⊤ v w
h : ¬Adj G v w
⊢ Adj (G ⊔ Gᶜ) v w
[PROOFSTEP]
exact Or.inr ⟨hvw, h⟩
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
src✝ : DistribLattice (SimpleGraph V) := distribLattice
x y : SimpleGraph V
⊢ x \ y = x ⊓ yᶜ
[PROOFSTEP]
ext v w
[GOAL]
case Adj.h.h.a
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
src✝ : DistribLattice (SimpleGraph V) := distribLattice
x y : SimpleGraph V
v w : V
⊢ Adj (x \ y) v w ↔ Adj (x ⊓ yᶜ) v w
[PROOFSTEP]
refine' ⟨fun h => ⟨h.1, ⟨_, h.2⟩⟩, fun h => ⟨h.1, h.2.2⟩⟩
[GOAL]
case Adj.h.h.a
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
src✝ : DistribLattice (SimpleGraph V) := distribLattice
x y : SimpleGraph V
v w : V
h : Adj (x \ y) v w
⊢ v ≠ w
[PROOFSTEP]
rintro rfl
[GOAL]
case Adj.h.h.a
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
src✝ : DistribLattice (SimpleGraph V) := distribLattice
x y : SimpleGraph V
v : V
h : Adj (x \ y) v v
⊢ False
[PROOFSTEP]
exact x.irrefl h.1
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G₁ G₂ : SimpleGraph V
⊢ edgeSet (G₁ ⊔ G₂) = edgeSet G₁ ∪ edgeSet G₂
[PROOFSTEP]
ext ⟨x, y⟩
[GOAL]
case h.mk.mk
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G₁ G₂ : SimpleGraph V
x✝ : Sym2 V
x y : V
⊢ Quot.mk Setoid.r (x, y) ∈ edgeSet (G₁ ⊔ G₂) ↔ Quot.mk Setoid.r (x, y) ∈ edgeSet G₁ ∪ edgeSet G₂
[PROOFSTEP]
rfl
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G₁ G₂ : SimpleGraph V
⊢ edgeSet (G₁ ⊓ G₂) = edgeSet G₁ ∩ edgeSet G₂
[PROOFSTEP]
ext ⟨x, y⟩
[GOAL]
case h.mk.mk
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G₁ G₂ : SimpleGraph V
x✝ : Sym2 V
x y : V
⊢ Quot.mk Setoid.r (x, y) ∈ edgeSet (G₁ ⊓ G₂) ↔ Quot.mk Setoid.r (x, y) ∈ edgeSet G₁ ∩ edgeSet G₂
[PROOFSTEP]
rfl
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G₁ G₂ : SimpleGraph V
⊢ edgeSet (G₁ \ G₂) = edgeSet G₁ \ edgeSet G₂
[PROOFSTEP]
ext ⟨x, y⟩
[GOAL]
case h.mk.mk
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G₁ G₂ : SimpleGraph V
x✝ : Sym2 V
x y : V
⊢ Quot.mk Setoid.r (x, y) ∈ edgeSet (G₁ \ G₂) ↔ Quot.mk Setoid.r (x, y) ∈ edgeSet G₁ \ edgeSet G₂
[PROOFSTEP]
rfl
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G₁ G₂ G : SimpleGraph V
s : Set (Sym2 V)
⊢ edgeSet G \ (s \ {e | Sym2.IsDiag e}) = edgeSet G \ s
[PROOFSTEP]
ext e
[GOAL]
case h
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e✝ : Sym2 V
G₁ G₂ G : SimpleGraph V
s : Set (Sym2 V)
e : Sym2 V
⊢ e ∈ edgeSet G \ (s \ {e | Sym2.IsDiag e}) ↔ e ∈ edgeSet G \ s
[PROOFSTEP]
simp only [Set.mem_diff, Set.mem_setOf_eq, not_and, not_not, and_congr_right_iff]
[GOAL]
case h
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e✝ : Sym2 V
G₁ G₂ G : SimpleGraph V
s : Set (Sym2 V)
e : Sym2 V
⊢ e ∈ edgeSet G → (e ∈ s → Sym2.IsDiag e ↔ ¬e ∈ s)
[PROOFSTEP]
intro h
[GOAL]
case h
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e✝ : Sym2 V
G₁ G₂ G : SimpleGraph V
s : Set (Sym2 V)
e : Sym2 V
h : e ∈ edgeSet G
⊢ e ∈ s → Sym2.IsDiag e ↔ ¬e ∈ s
[PROOFSTEP]
simp only [G.not_isDiag_of_mem_edgeSet h, imp_false]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
G₁ G₂ : SimpleGraph V
v w : V
⊢ Adj G v w ↔ v ≠ w ∧ ∃ e, e ∈ edgeSet G ∧ v ∈ e ∧ w ∈ e
[PROOFSTEP]
refine' ⟨fun _ => ⟨G.ne_of_adj ‹_›, ⟦(v, w)⟧, by simpa⟩, _⟩
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
G₁ G₂ : SimpleGraph V
v w : V
x✝ : Adj G v w
⊢ Quotient.mk (Sym2.Rel.setoid V) (v, w) ∈ edgeSet G ∧
    v ∈ Quotient.mk (Sym2.Rel.setoid V) (v, w) ∧ w ∈ Quotient.mk (Sym2.Rel.setoid V) (v, w)
[PROOFSTEP]
simpa
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
G₁ G₂ : SimpleGraph V
v w : V
⊢ (v ≠ w ∧ ∃ e, e ∈ edgeSet G ∧ v ∈ e ∧ w ∈ e) → Adj G v w
[PROOFSTEP]
rintro ⟨hne, e, he, hv⟩
[GOAL]
case intro.intro.intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e✝ : Sym2 V
G₁ G₂ : SimpleGraph V
v w : V
hne : v ≠ w
e : Sym2 V
he : e ∈ edgeSet G
hv : v ∈ e ∧ w ∈ e
⊢ Adj G v w
[PROOFSTEP]
rw [Sym2.mem_and_mem_iff hne] at hv 
[GOAL]
case intro.intro.intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e✝ : Sym2 V
G₁ G₂ : SimpleGraph V
v w : V
hne : v ≠ w
e : Sym2 V
he : e ∈ edgeSet G
hv : e = Quotient.mk (Sym2.Rel.setoid V) (v, w)
⊢ Adj G v w
[PROOFSTEP]
subst e
[GOAL]
case intro.intro.intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
G₁ G₂ : SimpleGraph V
v w : V
hne : v ≠ w
he : Quotient.mk (Sym2.Rel.setoid V) (v, w) ∈ edgeSet G
⊢ Adj G v w
[PROOFSTEP]
rwa [mem_edgeSet] at he 
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G₁ G₂ : SimpleGraph V
⊢ Adj G a b ↔ ∃ e, ↑e = Quotient.mk (Sym2.Rel.setoid V) (a, b)
[PROOFSTEP]
simp only [mem_edgeSet, exists_prop, SetCoe.exists, exists_eq_right, Subtype.coe_mk]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e✝ : Sym2 V
G₁ G₂ : SimpleGraph V
e : Sym2 V
he : e ∈ edgeSet G
v : V
h : v ∈ e
⊢ Sym2.Mem.other h ≠ v
[PROOFSTEP]
erw [← Sym2.other_spec h, Sym2.eq_swap] at he 
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e✝ : Sym2 V
G₁ G₂ : SimpleGraph V
e : Sym2 V
v : V
h : v ∈ e
he : Quotient.mk (Sym2.Rel.setoid V) (Sym2.Mem.other h, v) ∈ edgeSet G
⊢ Sym2.Mem.other h ≠ v
[PROOFSTEP]
exact G.ne_of_adj he
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G₁ G₂ : SimpleGraph V
⊢ Fintype ↑(edgeSet ⊥)
[PROOFSTEP]
rw [edgeSet_bot]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G₁ G₂ : SimpleGraph V
⊢ Fintype ↑∅
[PROOFSTEP]
infer_instance
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G₁ G₂ : SimpleGraph V
inst✝² : DecidableEq V
inst✝¹ : Fintype ↑(edgeSet G₁)
inst✝ : Fintype ↑(edgeSet G₂)
⊢ Fintype ↑(edgeSet (G₁ ⊔ G₂))
[PROOFSTEP]
rw [edgeSet_sup]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G₁ G₂ : SimpleGraph V
inst✝² : DecidableEq V
inst✝¹ : Fintype ↑(edgeSet G₁)
inst✝ : Fintype ↑(edgeSet G₂)
⊢ Fintype ↑(edgeSet G₁ ∪ edgeSet G₂)
[PROOFSTEP]
infer_instance
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G₁ G₂ : SimpleGraph V
inst✝² : DecidableEq V
inst✝¹ : Fintype ↑(edgeSet G₁)
inst✝ : Fintype ↑(edgeSet G₂)
⊢ Fintype ↑(edgeSet (G₁ ⊓ G₂))
[PROOFSTEP]
rw [edgeSet_inf]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G₁ G₂ : SimpleGraph V
inst✝² : DecidableEq V
inst✝¹ : Fintype ↑(edgeSet G₁)
inst✝ : Fintype ↑(edgeSet G₂)
⊢ Fintype ↑(edgeSet G₁ ∩ edgeSet G₂)
[PROOFSTEP]
exact Set.fintypeInter _ _
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G₁ G₂ : SimpleGraph V
inst✝² : DecidableEq V
inst✝¹ : Fintype ↑(edgeSet G₁)
inst✝ : Fintype ↑(edgeSet G₂)
⊢ Fintype ↑(edgeSet (G₁ \ G₂))
[PROOFSTEP]
rw [edgeSet_sdiff]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G₁ G₂ : SimpleGraph V
inst✝² : DecidableEq V
inst✝¹ : Fintype ↑(edgeSet G₁)
inst✝ : Fintype ↑(edgeSet G₂)
⊢ Fintype ↑(edgeSet G₁ \ edgeSet G₂)
[PROOFSTEP]
exact Set.fintypeDiff _ _
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
s : Set (Sym2 V)
⊢ edgeSet (fromEdgeSet s) = s \ {e | Sym2.IsDiag e}
[PROOFSTEP]
ext e
[GOAL]
case h
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e✝ : Sym2 V
s : Set (Sym2 V)
e : Sym2 V
⊢ e ∈ edgeSet (fromEdgeSet s) ↔ e ∈ s \ {e | Sym2.IsDiag e}
[PROOFSTEP]
exact Sym2.ind (by simp) e
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e✝ : Sym2 V
s : Set (Sym2 V)
e : Sym2 V
⊢ ∀ (x y : V),
    Quotient.mk (Sym2.Rel.setoid V) (x, y) ∈ edgeSet (fromEdgeSet s) ↔
      Quotient.mk (Sym2.Rel.setoid V) (x, y) ∈ s \ {e | Sym2.IsDiag e}
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
s : Set (Sym2 V)
⊢ fromEdgeSet (edgeSet G) = G
[PROOFSTEP]
ext v w
[GOAL]
case Adj.h.h.a
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
s : Set (Sym2 V)
v w : V
⊢ Adj (fromEdgeSet (edgeSet G)) v w ↔ Adj G v w
[PROOFSTEP]
exact ⟨fun h => h.1, fun h => ⟨h, G.ne_of_adj h⟩⟩
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
s : Set (Sym2 V)
⊢ fromEdgeSet ∅ = ⊥
[PROOFSTEP]
ext v w
[GOAL]
case Adj.h.h.a
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
s : Set (Sym2 V)
v w : V
⊢ Adj (fromEdgeSet ∅) v w ↔ Adj ⊥ v w
[PROOFSTEP]
simp only [fromEdgeSet_adj, Set.mem_empty_iff_false, false_and_iff, bot_adj]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
s : Set (Sym2 V)
⊢ fromEdgeSet Set.univ = ⊤
[PROOFSTEP]
ext v w
[GOAL]
case Adj.h.h.a
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
s : Set (Sym2 V)
v w : V
⊢ Adj (fromEdgeSet Set.univ) v w ↔ Adj ⊤ v w
[PROOFSTEP]
simp only [fromEdgeSet_adj, Set.mem_univ, true_and_iff, top_adj]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
s✝ s t : Set (Sym2 V)
⊢ fromEdgeSet s ⊓ fromEdgeSet t = fromEdgeSet (s ∩ t)
[PROOFSTEP]
ext v w
[GOAL]
case Adj.h.h.a
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
s✝ s t : Set (Sym2 V)
v w : V
⊢ Adj (fromEdgeSet s ⊓ fromEdgeSet t) v w ↔ Adj (fromEdgeSet (s ∩ t)) v w
[PROOFSTEP]
simp only [fromEdgeSet_adj, Set.mem_inter_iff, Ne.def, inf_adj]
[GOAL]
case Adj.h.h.a
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
s✝ s t : Set (Sym2 V)
v w : V
⊢ (Quotient.mk (Sym2.Rel.setoid V) (v, w) ∈ s ∧ ¬v = w) ∧ Quotient.mk (Sym2.Rel.setoid V) (v, w) ∈ t ∧ ¬v = w ↔
    (Quotient.mk (Sym2.Rel.setoid V) (v, w) ∈ s ∧ Quotient.mk (Sym2.Rel.setoid V) (v, w) ∈ t) ∧ ¬v = w
[PROOFSTEP]
tauto
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
s✝ s t : Set (Sym2 V)
⊢ fromEdgeSet s ⊔ fromEdgeSet t = fromEdgeSet (s ∪ t)
[PROOFSTEP]
ext v w
[GOAL]
case Adj.h.h.a
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
s✝ s t : Set (Sym2 V)
v w : V
⊢ Adj (fromEdgeSet s ⊔ fromEdgeSet t) v w ↔ Adj (fromEdgeSet (s ∪ t)) v w
[PROOFSTEP]
simp [Set.mem_union, or_and_right]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
s✝ s t : Set (Sym2 V)
⊢ fromEdgeSet s \ fromEdgeSet t = fromEdgeSet (s \ t)
[PROOFSTEP]
ext v w
[GOAL]
case Adj.h.h.a
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
s✝ s t : Set (Sym2 V)
v w : V
⊢ Adj (fromEdgeSet s \ fromEdgeSet t) v w ↔ Adj (fromEdgeSet (s \ t)) v w
[PROOFSTEP]
constructor
[GOAL]
case Adj.h.h.a.mp
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
s✝ s t : Set (Sym2 V)
v w : V
⊢ Adj (fromEdgeSet s \ fromEdgeSet t) v w → Adj (fromEdgeSet (s \ t)) v w
[PROOFSTEP]
simp (config := { contextual := true })
[GOAL]
case Adj.h.h.a.mpr
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
s✝ s t : Set (Sym2 V)
v w : V
⊢ Adj (fromEdgeSet (s \ t)) v w → Adj (fromEdgeSet s \ fromEdgeSet t) v w
[PROOFSTEP]
simp (config := { contextual := true })
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
s✝ s t : Set (Sym2 V)
h : s ⊆ t
⊢ fromEdgeSet s ≤ fromEdgeSet t
[PROOFSTEP]
rintro v w
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
s✝ s t : Set (Sym2 V)
h : s ⊆ t
v w : V
⊢ Adj (fromEdgeSet s) v w → Adj (fromEdgeSet t) v w
[PROOFSTEP]
simp (config := { contextual := true }) only [fromEdgeSet_adj, Ne.def, not_false_iff, and_true_iff, and_imp]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
s✝ s t : Set (Sym2 V)
h : s ⊆ t
v w : V
⊢ Quotient.mk (Sym2.Rel.setoid V) (v, w) ∈ s → ¬v = w → Quotient.mk (Sym2.Rel.setoid V) (v, w) ∈ t
[PROOFSTEP]
exact fun vws _ => h vws
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
s : Set (Sym2 V)
inst✝¹ : DecidableEq V
inst✝ : Fintype ↑s
⊢ Fintype ↑(edgeSet (fromEdgeSet s))
[PROOFSTEP]
rw [edgeSet_fromEdgeSet s]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
s : Set (Sym2 V)
inst✝¹ : DecidableEq V
inst✝ : Fintype ↑s
⊢ Fintype ↑(s \ {e | Sym2.IsDiag e})
[PROOFSTEP]
infer_instance
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
d₁ d₂ : Dart G
⊢ d₁ = d₂ ↔ d₁.toProd = d₂.toProd
[PROOFSTEP]
cases d₁
[GOAL]
case mk
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
d₂ : Dart G
toProd✝ : V × V
is_adj✝ : Adj G toProd✝.fst toProd✝.snd
⊢ { toProd := toProd✝, is_adj := is_adj✝ } = d₂ ↔ { toProd := toProd✝, is_adj := is_adj✝ }.toProd = d₂.toProd
[PROOFSTEP]
cases d₂
[GOAL]
case mk.mk
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
toProd✝¹ : V × V
is_adj✝¹ : Adj G toProd✝¹.fst toProd✝¹.snd
toProd✝ : V × V
is_adj✝ : Adj G toProd✝.fst toProd✝.snd
⊢ { toProd := toProd✝¹, is_adj := is_adj✝¹ } = { toProd := toProd✝, is_adj := is_adj✝ } ↔
    { toProd := toProd✝¹, is_adj := is_adj✝¹ }.toProd = { toProd := toProd✝, is_adj := is_adj✝ }.toProd
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableRel G.Adj
s : (v : V) × ↑(neighborSet G v)
⊢ (fun d => { fst := d.fst, snd := { val := d.snd, property := (_ : Adj G d.fst d.snd) } })
      ((fun s => { toProd := (s.fst, ↑s.snd), is_adj := (_ : ↑s.snd ∈ neighborSet G s.fst) }) s) =
    s
[PROOFSTEP]
ext
[GOAL]
case a
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableRel G.Adj
s : (v : V) × ↑(neighborSet G v)
⊢ ((fun d => { fst := d.fst, snd := { val := d.snd, property := (_ : Adj G d.fst d.snd) } })
        ((fun s => { toProd := (s.fst, ↑s.snd), is_adj := (_ : ↑s.snd ∈ neighborSet G s.fst) }) s)).fst =
    s.fst
[PROOFSTEP]
simp
[GOAL]
case a
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableRel G.Adj
s : (v : V) × ↑(neighborSet G v)
⊢ ↑((fun d => { fst := d.fst, snd := { val := d.snd, property := (_ : Adj G d.fst d.snd) } })
          ((fun s => { toProd := (s.fst, ↑s.snd), is_adj := (_ : ↑s.snd ∈ neighborSet G s.fst) }) s)).snd =
    ↑s.snd
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableRel G.Adj
d : Dart G
⊢ (fun s => { toProd := (s.fst, ↑s.snd), is_adj := (_ : ↑s.snd ∈ neighborSet G s.fst) })
      ((fun d => { fst := d.fst, snd := { val := d.snd, property := (_ : Adj G d.fst d.snd) } }) d) =
    d
[PROOFSTEP]
ext
[GOAL]
case h.h₁
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableRel G.Adj
d : Dart G
⊢ ((fun s => { toProd := (s.fst, ↑s.snd), is_adj := (_ : ↑s.snd ∈ neighborSet G s.fst) })
        ((fun d => { fst := d.fst, snd := { val := d.snd, property := (_ : Adj G d.fst d.snd) } }) d)).fst =
    d.fst
[PROOFSTEP]
simp
[GOAL]
case h.h₂
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableRel G.Adj
d : Dart G
⊢ ((fun s => { toProd := (s.fst, ↑s.snd), is_adj := (_ : ↑s.snd ∈ neighborSet G s.fst) })
        ((fun d => { fst := d.fst, snd := { val := d.snd, property := (_ : Adj G d.fst d.snd) } }) d)).snd =
    d.snd
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
⊢ ∀ (d₁ d₂ : Dart G), Dart.edge d₁ = Dart.edge d₂ ↔ d₁ = d₂ ∨ d₁ = Dart.symm d₂
[PROOFSTEP]
rintro ⟨p, hp⟩ ⟨q, hq⟩
[GOAL]
case mk.mk
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
p : V × V
hp : Adj G p.fst p.snd
q : V × V
hq : Adj G q.fst q.snd
⊢ Dart.edge { toProd := p, is_adj := hp } = Dart.edge { toProd := q, is_adj := hq } ↔
    { toProd := p, is_adj := hp } = { toProd := q, is_adj := hq } ∨
      { toProd := p, is_adj := hp } = Dart.symm { toProd := q, is_adj := hq }
[PROOFSTEP]
simp [Sym2.mk''_eq_mk''_iff, -Quotient.eq]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
⊢ ∀ {d : Dart G} {p : V × V}, Dart.edge d = Quotient.mk (Sym2.Rel.setoid V) p ↔ d.toProd = p ∨ d.toProd = Prod.swap p
[PROOFSTEP]
rintro ⟨p, h⟩
[GOAL]
case mk
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
p : V × V
h : Adj G p.fst p.snd
⊢ ∀ {p_1 : V × V},
    Dart.edge { toProd := p, is_adj := h } = Quotient.mk (Sym2.Rel.setoid V) p_1 ↔
      { toProd := p, is_adj := h }.toProd = p_1 ∨ { toProd := p, is_adj := h }.toProd = Prod.swap p_1
[PROOFSTEP]
apply Sym2.mk''_eq_mk''_iff
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
⊢ ∀ {d : Dart G} {u v : V},
    Dart.edge d = Quotient.mk (Sym2.Rel.setoid V) (u, v) ↔ d.fst = u ∧ d.snd = v ∨ d.fst = v ∧ d.snd = u
[PROOFSTEP]
rintro ⟨⟨a, b⟩, h⟩ u v
[GOAL]
case mk.mk
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a✝ b✝ c u✝ v✝ w : V
e : Sym2 V
a b : V
h : Adj G (a, b).fst (a, b).snd
u v : V
⊢ Dart.edge { toProd := (a, b), is_adj := h } = Quotient.mk (Sym2.Rel.setoid V) (u, v) ↔
    { toProd := (a, b), is_adj := h }.toProd.fst = u ∧ { toProd := (a, b), is_adj := h }.toProd.snd = v ∨
      { toProd := (a, b), is_adj := h }.toProd.fst = v ∧ { toProd := (a, b), is_adj := h }.toProd.snd = u
[PROOFSTEP]
rw [dart_edge_eq_mk'_iff]
[GOAL]
case mk.mk
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a✝ b✝ c u✝ v✝ w : V
e : Sym2 V
a b : V
h : Adj G (a, b).fst (a, b).snd
u v : V
⊢ { toProd := (a, b), is_adj := h }.toProd = (u, v) ∨ { toProd := (a, b), is_adj := h }.toProd = Prod.swap (u, v) ↔
    { toProd := (a, b), is_adj := h }.toProd.fst = u ∧ { toProd := (a, b), is_adj := h }.toProd.snd = v ∨
      { toProd := (a, b), is_adj := h }.toProd.fst = v ∧ { toProd := (a, b), is_adj := h }.toProd.snd = u
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
v : V
e₁ e₂ : ↑(neighborSet G v)
h : dartOfNeighborSet G v e₁ = dartOfNeighborSet G v e₂
⊢ ↑e₁ = ↑e₂
[PROOFSTEP]
injection h with h'
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
v : V
e₁ e₂ : ↑(neighborSet G v)
h' : (v, ↑e₁) = (v, ↑e₂)
⊢ ↑e₁ = ↑e₂
[PROOFSTEP]
convert congr_arg Prod.snd h'
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝ : Nontrivial V
⊢ Nonempty (Dart ⊤)
[PROOFSTEP]
obtain ⟨v, w, h⟩ := exists_pair_ne V
[GOAL]
case intro.intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
inst✝ : Nontrivial V
v w : V
h : v ≠ w
⊢ Nonempty (Dart ⊤)
[PROOFSTEP]
exact ⟨⟨(v, w), h⟩⟩
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
h : Adj G a b
⊢ incidenceSet G a ∩ incidenceSet G b = {Quotient.mk (Sym2.Rel.setoid V) (a, b)}
[PROOFSTEP]
refine' (G.incidenceSet_inter_incidenceSet_subset <| h.ne).antisymm _
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
h : Adj G a b
⊢ {Quotient.mk (Sym2.Rel.setoid V) (a, b)} ⊆ incidenceSet G a ∩ incidenceSet G b
[PROOFSTEP]
rintro _ (rfl : _ = ⟦(a, b)⟧)
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
h : Adj G a b
⊢ Quotient.mk (Sym2.Rel.setoid V) (a, b) ∈ incidenceSet G a ∩ incidenceSet G b
[PROOFSTEP]
exact ⟨G.mk'_mem_incidenceSet_left_iff.2 h, G.mk'_mem_incidenceSet_right_iff.2 h⟩
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
h : a ≠ b
ha : e ∈ incidenceSet G a
hb : e ∈ incidenceSet G b
⊢ Adj G a b
[PROOFSTEP]
rwa [← mk'_mem_incidenceSet_left_iff, ← Set.mem_singleton_iff.1 <| G.incidenceSet_inter_incidenceSet_subset h ⟨ha, hb⟩]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
h : ¬Adj G a b
hn : a ≠ b
⊢ incidenceSet G a ∩ incidenceSet G b = ∅
[PROOFSTEP]
simp_rw [Set.eq_empty_iff_forall_not_mem, Set.mem_inter_iff, not_and]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
h : ¬Adj G a b
hn : a ≠ b
⊢ ∀ (x : Sym2 V), x ∈ incidenceSet G a → ¬x ∈ incidenceSet G b
[PROOFSTEP]
intro u ha hb
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u✝ v w : V
e : Sym2 V
h : ¬Adj G a b
hn : a ≠ b
u : Sym2 V
ha : u ∈ incidenceSet G a
hb : u ∈ incidenceSet G b
⊢ False
[PROOFSTEP]
exact h (G.adj_of_mem_incidenceSet hn ha hb)
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G₁ G₂ : SimpleGraph V
inst✝² : Fintype ↑(edgeSet G)
inst✝¹ : Fintype ↑(edgeSet G₁)
inst✝ : Fintype ↑(edgeSet G₂)
⊢ edgeFinset G₁ = edgeFinset G₂ ↔ G₁ = G₂
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G₁ G₂ : SimpleGraph V
inst✝² : Fintype ↑(edgeSet G)
inst✝¹ : Fintype ↑(edgeSet G₁)
inst✝ : Fintype ↑(edgeSet G₂)
⊢ edgeFinset G₁ ⊆ edgeFinset G₂ ↔ G₁ ≤ G₂
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G₁ G₂ : SimpleGraph V
inst✝² : Fintype ↑(edgeSet G)
inst✝¹ : Fintype ↑(edgeSet G₁)
inst✝ : Fintype ↑(edgeSet G₂)
⊢ edgeFinset G₁ ⊂ edgeFinset G₂ ↔ G₁ < G₂
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G₁ G₂ : SimpleGraph V
inst✝² : Fintype ↑(edgeSet G)
inst✝¹ : Fintype ↑(edgeSet G₁)
inst✝ : Fintype ↑(edgeSet G₂)
⊢ edgeFinset ⊥ = ∅
[PROOFSTEP]
simp [edgeFinset]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G₁ G₂ : SimpleGraph V
inst✝³ : Fintype ↑(edgeSet G)
inst✝² : Fintype ↑(edgeSet G₁)
inst✝¹ : Fintype ↑(edgeSet G₂)
inst✝ : DecidableEq V
⊢ edgeFinset (G₁ ⊔ G₂) = edgeFinset G₁ ∪ edgeFinset G₂
[PROOFSTEP]
simp [edgeFinset]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G₁ G₂ : SimpleGraph V
inst✝³ : Fintype ↑(edgeSet G)
inst✝² : Fintype ↑(edgeSet G₁)
inst✝¹ : Fintype ↑(edgeSet G₂)
inst✝ : DecidableEq V
⊢ edgeFinset (G₁ ⊓ G₂) = edgeFinset G₁ ∩ edgeFinset G₂
[PROOFSTEP]
simp [edgeFinset]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G₁ G₂ : SimpleGraph V
inst✝³ : Fintype ↑(edgeSet G)
inst✝² : Fintype ↑(edgeSet G₁)
inst✝¹ : Fintype ↑(edgeSet G₂)
inst✝ : DecidableEq V
⊢ edgeFinset (G₁ \ G₂) = edgeFinset G₁ \ edgeFinset G₂
[PROOFSTEP]
simp [edgeFinset]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
v w : V
⊢ Quotient.mk (Sym2.Rel.setoid V) (v, w) ∈ incidenceSet G v ↔ Adj G v w
[PROOFSTEP]
simp [incidenceSet]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
v w : V
⊢ Quotient.mk (Sym2.Rel.setoid V) (v, w) ∈ incidenceSet G v ↔ w ∈ neighborSet G v
[PROOFSTEP]
simp only [mem_incidenceSet, mem_neighborSet]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e✝ : Sym2 V
v : V
e : Sym2 V
he : e ∈ edgeSet G
h : v ∈ e
⊢ incidenceSet G v ∩ incidenceSet G (Sym2.Mem.other h) = {e}
[PROOFSTEP]
ext e'
[GOAL]
case h
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e✝ : Sym2 V
v : V
e : Sym2 V
he : e ∈ edgeSet G
h : v ∈ e
e' : Sym2 V
⊢ e' ∈ incidenceSet G v ∩ incidenceSet G (Sym2.Mem.other h) ↔ e' ∈ {e}
[PROOFSTEP]
simp only [incidenceSet, Set.mem_sep_iff, Set.mem_inter_iff, Set.mem_singleton_iff]
[GOAL]
case h
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e✝ : Sym2 V
v : V
e : Sym2 V
he : e ∈ edgeSet G
h : v ∈ e
e' : Sym2 V
⊢ (e' ∈ edgeSet G ∧ v ∈ e') ∧ e' ∈ edgeSet G ∧ Sym2.Mem.other h ∈ e' ↔ e' = e
[PROOFSTEP]
refine' ⟨fun h' => _, _⟩
[GOAL]
case h.refine'_1
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e✝ : Sym2 V
v : V
e : Sym2 V
he : e ∈ edgeSet G
h : v ∈ e
e' : Sym2 V
h' : (e' ∈ edgeSet G ∧ v ∈ e') ∧ e' ∈ edgeSet G ∧ Sym2.Mem.other h ∈ e'
⊢ e' = e
[PROOFSTEP]
rw [← Sym2.other_spec h]
[GOAL]
case h.refine'_1
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e✝ : Sym2 V
v : V
e : Sym2 V
he : e ∈ edgeSet G
h : v ∈ e
e' : Sym2 V
h' : (e' ∈ edgeSet G ∧ v ∈ e') ∧ e' ∈ edgeSet G ∧ Sym2.Mem.other h ∈ e'
⊢ e' = Quotient.mk (Sym2.Rel.setoid V) (v, Sym2.Mem.other h)
[PROOFSTEP]
exact (Sym2.mem_and_mem_iff (edge_other_ne G he h).symm).mp ⟨h'.1.2, h'.2.2⟩
[GOAL]
case h.refine'_2
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e✝ : Sym2 V
v : V
e : Sym2 V
he : e ∈ edgeSet G
h : v ∈ e
e' : Sym2 V
⊢ e' = e → (e' ∈ edgeSet G ∧ v ∈ e') ∧ e' ∈ edgeSet G ∧ Sym2.Mem.other h ∈ e'
[PROOFSTEP]
rintro rfl
[GOAL]
case h.refine'_2
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
v : V
e' : Sym2 V
he : e' ∈ edgeSet G
h : v ∈ e'
⊢ (e' ∈ edgeSet G ∧ v ∈ e') ∧ e' ∈ edgeSet G ∧ Sym2.Mem.other h ∈ e'
[PROOFSTEP]
exact ⟨⟨he, h⟩, he, Sym2.other_mem _⟩
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
G : SimpleGraph V
v : V
⊢ Disjoint (neighborSet G v) (neighborSet Gᶜ v)
[PROOFSTEP]
rw [Set.disjoint_iff]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
G : SimpleGraph V
v : V
⊢ neighborSet G v ∩ neighborSet Gᶜ v ⊆ ∅
[PROOFSTEP]
rintro w ⟨h, h'⟩
[GOAL]
case intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
G : SimpleGraph V
v w : V
h : w ∈ neighborSet G v
h' : w ∈ neighborSet Gᶜ v
⊢ w ∈ ∅
[PROOFSTEP]
rw [mem_neighborSet, compl_adj] at h' 
[GOAL]
case intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
G : SimpleGraph V
v w : V
h : w ∈ neighborSet G v
h' : v ≠ w ∧ ¬Adj G v w
⊢ w ∈ ∅
[PROOFSTEP]
exact h'.2 h
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
G : SimpleGraph V
v : V
⊢ neighborSet G v ∪ neighborSet Gᶜ v = {v}ᶜ
[PROOFSTEP]
ext w
[GOAL]
case h
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
G : SimpleGraph V
v w : V
⊢ w ∈ neighborSet G v ∪ neighborSet Gᶜ v ↔ w ∈ {v}ᶜ
[PROOFSTEP]
have h := @ne_of_adj _ G
[GOAL]
case h
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
G : SimpleGraph V
v w : V
h : ∀ {a b : V}, Adj G a b → a ≠ b
⊢ w ∈ neighborSet G v ∪ neighborSet Gᶜ v ↔ w ∈ {v}ᶜ
[PROOFSTEP]
simp_rw [Set.mem_union, mem_neighborSet, compl_adj, Set.mem_compl_iff, Set.mem_singleton_iff]
[GOAL]
case h
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
G : SimpleGraph V
v w : V
h : ∀ {a b : V}, Adj G a b → a ≠ b
⊢ Adj G v w ∨ v ≠ w ∧ ¬Adj G v w ↔ ¬w = v
[PROOFSTEP]
tauto
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝¹ : Fintype V
G : SimpleGraph V
v : V
inst✝ : Fintype ↑(neighborSet G v ∪ neighborSet Gᶜ v)
⊢ card (Set.toFinset (neighborSet G v ∪ neighborSet Gᶜ v)) = Fintype.card V - 1
[PROOFSTEP]
classical simp_rw [neighborSet_union_compl_neighborSet_eq, Set.toFinset_compl, Finset.card_compl, Set.toFinset_card,
  Set.card_singleton]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝¹ : Fintype V
G : SimpleGraph V
v : V
inst✝ : Fintype ↑(neighborSet G v ∪ neighborSet Gᶜ v)
⊢ card (Set.toFinset (neighborSet G v ∪ neighborSet Gᶜ v)) = Fintype.card V - 1
[PROOFSTEP]
simp_rw [neighborSet_union_compl_neighborSet_eq, Set.toFinset_compl, Finset.card_compl, Set.toFinset_card,
  Set.card_singleton]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
G : SimpleGraph V
v : V
⊢ neighborSet Gᶜ v = (neighborSet G v)ᶜ \ {v}
[PROOFSTEP]
ext w
[GOAL]
case h
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
G : SimpleGraph V
v w : V
⊢ w ∈ neighborSet Gᶜ v ↔ w ∈ (neighborSet G v)ᶜ \ {v}
[PROOFSTEP]
simp [and_comm, eq_comm]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
v w : V
⊢ commonNeighbors ⊤ v w = Set.univ \ {v, w}
[PROOFSTEP]
ext u
[GOAL]
case h
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u✝ v✝ w✝ : V
e : Sym2 V
v w u : V
⊢ u ∈ commonNeighbors ⊤ v w ↔ u ∈ Set.univ \ {v, w}
[PROOFSTEP]
simp [commonNeighbors, eq_comm, not_or]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e✝ : Sym2 V
inst✝ : DecidableEq V
v : V
e : Sym2 V
h : e ∈ incidenceSet G v
⊢ e ∈ incidenceSet G (otherVertexOfIncident G h)
[PROOFSTEP]
use h.1
[GOAL]
case right
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e✝ : Sym2 V
inst✝ : DecidableEq V
v : V
e : Sym2 V
h : e ∈ incidenceSet G v
⊢ otherVertexOfIncident G h ∈ e
[PROOFSTEP]
simp [otherVertexOfIncident, Sym2.other_mem']
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e✝ : Sym2 V
inst✝ : DecidableEq V
v : V
e : Sym2 V
h : e ∈ incidenceSet G v
⊢ otherVertexOfIncident G h ∈ neighborSet G v
[PROOFSTEP]
cases' h with he hv
[GOAL]
case intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e✝ : Sym2 V
inst✝ : DecidableEq V
v : V
e : Sym2 V
he : e ∈ edgeSet G
hv : v ∈ e
⊢ otherVertexOfIncident G (_ : e ∈ edgeSet G ∧ v ∈ e) ∈ neighborSet G v
[PROOFSTEP]
rwa [← Sym2.other_spec' hv, mem_edgeSet] at he 
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝ : DecidableEq V
v : V
x : ↑(incidenceSet G v)
⊢ (fun w =>
        { val := Quotient.mk (Sym2.Rel.setoid V) (v, ↑w),
          property := (_ : Quotient.mk (Sym2.Rel.setoid V) (v, ↑w) ∈ incidenceSet G v) })
      ((fun e =>
          { val := otherVertexOfIncident G (_ : ↑e ∈ incidenceSet G v),
            property := (_ : otherVertexOfIncident G (_ : ↑e ∈ incidenceSet G v) ∈ neighborSet G v) })
        x) =
    x
[PROOFSTEP]
simp [otherVertexOfIncident]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
inst✝ : DecidableEq V
v : V
x✝ : ↑(neighborSet G v)
w : V
hw : w ∈ neighborSet G v
⊢ (fun e =>
        { val := otherVertexOfIncident G (_ : ↑e ∈ incidenceSet G v),
          property := (_ : otherVertexOfIncident G (_ : ↑e ∈ incidenceSet G v) ∈ neighborSet G v) })
      ((fun w =>
          { val := Quotient.mk (Sym2.Rel.setoid V) (v, ↑w),
            property := (_ : Quotient.mk (Sym2.Rel.setoid V) (v, ↑w) ∈ incidenceSet G v) })
        { val := w, property := hw }) =
    { val := w, property := hw }
[PROOFSTEP]
simp only [mem_neighborSet, Subtype.mk.injEq]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
inst✝ : DecidableEq V
v : V
x✝ : ↑(neighborSet G v)
w : V
hw : w ∈ neighborSet G v
⊢ otherVertexOfIncident G
      (_ :
        ↑((fun w =>
                { val := Quotient.mk (Sym2.Rel.setoid V) (v, ↑w),
                  property := (_ : Quotient.mk (Sym2.Rel.setoid V) (v, ↑w) ∈ incidenceSet G v) })
              { val := w, property := hw }) ∈
          incidenceSet G v) =
    w
[PROOFSTEP]
exact incidence_other_neighbor_edge _ hw
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a✝ b✝ c u v w : V
e : Sym2 V
s : Set (Sym2 V)
a b : V
⊢ (G.Adj \ Sym2.ToRel s) a b → (G.Adj \ Sym2.ToRel s) b a
[PROOFSTEP]
simp [adj_comm, Sym2.eq_swap]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a✝ b c u v w : V
e : Sym2 V
s : Set (Sym2 V)
a : V
⊢ ¬(G.Adj \ Sym2.ToRel s) a a
[PROOFSTEP]
simp [SDiff.sdiff]
  -- porting note: used to be handled by `obviously`
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G'✝ : SimpleGraph W
a b c u v w : V
e : Sym2 V
G G' : SimpleGraph V
⊢ G \ G' = deleteEdges G (edgeSet G')
[PROOFSTEP]
ext
[GOAL]
case Adj.h.h.a
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G'✝ : SimpleGraph W
a b c u v w : V
e : Sym2 V
G G' : SimpleGraph V
x✝¹ x✝ : V
⊢ Adj (G \ G') x✝¹ x✝ ↔ Adj (deleteEdges G (edgeSet G')) x✝¹ x✝
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
s : Set (Sym2 V)
⊢ deleteEdges G s = G \ fromEdgeSet s
[PROOFSTEP]
ext
[GOAL]
case Adj.h.h.a
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
s : Set (Sym2 V)
x✝¹ x✝ : V
⊢ Adj (deleteEdges G s) x✝¹ x✝ ↔ Adj (G \ fromEdgeSet s) x✝¹ x✝
[PROOFSTEP]
exact ⟨fun h => ⟨h.1, not_and_of_not_left _ h.2⟩, fun h => ⟨h.1, not_and'.mp h.2 h.ne⟩⟩
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
⊢ Gᶜ = deleteEdges ⊤ (edgeSet G)
[PROOFSTEP]
ext
[GOAL]
case Adj.h.h.a
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
x✝¹ x✝ : V
⊢ Adj Gᶜ x✝¹ x✝ ↔ Adj (deleteEdges ⊤ (edgeSet G)) x✝¹ x✝
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
s s' : Set (Sym2 V)
⊢ deleteEdges (deleteEdges G s) s' = deleteEdges G (s ∪ s')
[PROOFSTEP]
ext
[GOAL]
case Adj.h.h.a
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
s s' : Set (Sym2 V)
x✝¹ x✝ : V
⊢ Adj (deleteEdges (deleteEdges G s) s') x✝¹ x✝ ↔ Adj (deleteEdges G (s ∪ s')) x✝¹ x✝
[PROOFSTEP]
simp [and_assoc, not_or]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
⊢ deleteEdges G ∅ = G
[PROOFSTEP]
ext
[GOAL]
case Adj.h.h.a
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
x✝¹ x✝ : V
⊢ Adj (deleteEdges G ∅) x✝¹ x✝ ↔ Adj G x✝¹ x✝
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
⊢ deleteEdges G Set.univ = ⊥
[PROOFSTEP]
ext
[GOAL]
case Adj.h.h.a
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
x✝¹ x✝ : V
⊢ Adj (deleteEdges G Set.univ) x✝¹ x✝ ↔ Adj ⊥ x✝¹ x✝
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
s : Set (Sym2 V)
⊢ deleteEdges G s ≤ G
[PROOFSTEP]
intro
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
s : Set (Sym2 V)
v✝ : V
⊢ ∀ ⦃w : V⦄, Adj (deleteEdges G s) v✝ w → Adj G v✝ w
[PROOFSTEP]
simp (config := { contextual := true })
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
s s' : Set (Sym2 V)
h : s ⊆ s'
v w : V
⊢ Adj (deleteEdges G s') v w → Adj (deleteEdges G s) v w
[PROOFSTEP]
simp (config := { contextual := true }) only [deleteEdges_adj, and_imp, true_and_iff]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
s s' : Set (Sym2 V)
h : s ⊆ s'
v w : V
⊢ Adj G v w → ¬Quotient.mk (Sym2.Rel.setoid V) (v, w) ∈ s' → ¬Quotient.mk (Sym2.Rel.setoid V) (v, w) ∈ s
[PROOFSTEP]
exact fun _ hn hs => hn (h hs)
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
s : Set (Sym2 V)
⊢ deleteEdges G s = deleteEdges G (s ∩ edgeSet G)
[PROOFSTEP]
ext
[GOAL]
case Adj.h.h.a
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
s : Set (Sym2 V)
x✝¹ x✝ : V
⊢ Adj (deleteEdges G s) x✝¹ x✝ ↔ Adj (deleteEdges G (s ∩ edgeSet G)) x✝¹ x✝
[PROOFSTEP]
simp (config := { contextual := true }) [imp_false]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
H : SimpleGraph V
h : H ≤ G
⊢ deleteEdges G (edgeSet G \ edgeSet H) = H
[PROOFSTEP]
ext v w
[GOAL]
case Adj.h.h.a
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
H : SimpleGraph V
h : H ≤ G
v w : V
⊢ Adj (deleteEdges G (edgeSet G \ edgeSet H)) v w ↔ Adj H v w
[PROOFSTEP]
constructor
[GOAL]
case Adj.h.h.a.mp
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
H : SimpleGraph V
h : H ≤ G
v w : V
⊢ Adj (deleteEdges G (edgeSet G \ edgeSet H)) v w → Adj H v w
[PROOFSTEP]
simp (config := { contextual := true }) [@h v w]
[GOAL]
case Adj.h.h.a.mpr
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
H : SimpleGraph V
h : H ≤ G
v w : V
⊢ Adj H v w → Adj (deleteEdges G (edgeSet G \ edgeSet H)) v w
[PROOFSTEP]
simp (config := { contextual := true }) [@h v w]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
s : Set (Sym2 V)
⊢ edgeSet (deleteEdges G s) = edgeSet G \ s
[PROOFSTEP]
ext e
[GOAL]
case h
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e✝ : Sym2 V
s : Set (Sym2 V)
e : Sym2 V
⊢ e ∈ edgeSet (deleteEdges G s) ↔ e ∈ edgeSet G \ s
[PROOFSTEP]
refine' Sym2.ind _ e
[GOAL]
case h
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e✝ : Sym2 V
s : Set (Sym2 V)
e : Sym2 V
⊢ ∀ (x y : V),
    Quotient.mk (Sym2.Rel.setoid V) (x, y) ∈ edgeSet (deleteEdges G s) ↔
      Quotient.mk (Sym2.Rel.setoid V) (x, y) ∈ edgeSet G \ s
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝³ : Fintype (Sym2 V)
inst✝² : DecidableEq V
inst✝¹ : DecidableRel G.Adj
s : Finset (Sym2 V)
inst✝ : DecidableRel (deleteEdges G ↑s).Adj
⊢ edgeFinset (deleteEdges G ↑s) = edgeFinset G \ s
[PROOFSTEP]
ext e
[GOAL]
case a
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e✝ : Sym2 V
inst✝³ : Fintype (Sym2 V)
inst✝² : DecidableEq V
inst✝¹ : DecidableRel G.Adj
s : Finset (Sym2 V)
inst✝ : DecidableRel (deleteEdges G ↑s).Adj
e : Sym2 V
⊢ e ∈ edgeFinset (deleteEdges G ↑s) ↔ e ∈ edgeFinset G \ s
[PROOFSTEP]
simp [edgeSet_deleteEdges]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝⁴ : OrderedRing 𝕜
inst✝³ : Fintype V
inst✝² : Fintype (Sym2 V)
inst✝¹ : DecidableEq V
inst✝ : DecidableRel G.Adj
p : SimpleGraph V → Prop
r r₁ r₂ : 𝕜
⊢ DeleteFar G p r ↔ ∀ ⦃H : SimpleGraph V⦄, H ≤ G → p H → r ≤ ↑(card (edgeFinset G)) - ↑(card (edgeFinset H))
[PROOFSTEP]
refine' ⟨fun h H hHG hH => _, fun h s hs hG => _⟩
[GOAL]
case refine'_1
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝⁴ : OrderedRing 𝕜
inst✝³ : Fintype V
inst✝² : Fintype (Sym2 V)
inst✝¹ : DecidableEq V
inst✝ : DecidableRel G.Adj
p : SimpleGraph V → Prop
r r₁ r₂ : 𝕜
h : DeleteFar G p r
H : SimpleGraph V
hHG : H ≤ G
hH : p H
⊢ r ≤ ↑(card (edgeFinset G)) - ↑(card (edgeFinset H))
[PROOFSTEP]
have := h (sdiff_subset G.edgeFinset H.edgeFinset)
[GOAL]
case refine'_1
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝⁴ : OrderedRing 𝕜
inst✝³ : Fintype V
inst✝² : Fintype (Sym2 V)
inst✝¹ : DecidableEq V
inst✝ : DecidableRel G.Adj
p : SimpleGraph V → Prop
r r₁ r₂ : 𝕜
h : DeleteFar G p r
H : SimpleGraph V
hHG : H ≤ G
hH : p H
this : p (deleteEdges G ↑(edgeFinset G \ edgeFinset H)) → r ≤ ↑(card (edgeFinset G \ edgeFinset H))
⊢ r ≤ ↑(card (edgeFinset G)) - ↑(card (edgeFinset H))
[PROOFSTEP]
simp only [deleteEdges_sdiff_eq_of_le _ hHG, edgeFinset_mono hHG, card_sdiff, card_le_of_subset, coe_sdiff,
  coe_edgeFinset, Nat.cast_sub] at this 
[GOAL]
case refine'_1
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝⁴ : OrderedRing 𝕜
inst✝³ : Fintype V
inst✝² : Fintype (Sym2 V)
inst✝¹ : DecidableEq V
inst✝ : DecidableRel G.Adj
p : SimpleGraph V → Prop
r r₁ r₂ : 𝕜
h : DeleteFar G p r
H : SimpleGraph V
hHG : H ≤ G
hH : p H
this : p H → r ≤ ↑(card (edgeFinset G)) - ↑(card (edgeFinset H))
⊢ r ≤ ↑(card (edgeFinset G)) - ↑(card (edgeFinset H))
[PROOFSTEP]
exact this hH
[GOAL]
case refine'_2
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝⁴ : OrderedRing 𝕜
inst✝³ : Fintype V
inst✝² : Fintype (Sym2 V)
inst✝¹ : DecidableEq V
inst✝ : DecidableRel G.Adj
p : SimpleGraph V → Prop
r r₁ r₂ : 𝕜
h : ∀ ⦃H : SimpleGraph V⦄, H ≤ G → p H → r ≤ ↑(card (edgeFinset G)) - ↑(card (edgeFinset H))
s : Finset (Sym2 V)
hs : s ⊆ edgeFinset G
hG : p (deleteEdges G ↑s)
⊢ r ≤ ↑(card s)
[PROOFSTEP]
simpa [card_sdiff hs, edgeFinset_deleteEdges, -Set.toFinset_card, Nat.cast_sub, card_le_of_subset hs] using
  h (G.deleteEdges_le s) hG
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a✝ b✝ c u v w : V
e : Sym2 V
f : V ↪ W
G : SimpleGraph V
a b : W
⊢ Relation.Map G.Adj (↑f) (↑f) a b → Relation.Map G.Adj (↑f) (↑f) b a
[PROOFSTEP]
rintro ⟨v, w, h, rfl, rfl⟩
[GOAL]
case intro.intro.intro.intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
f : V ↪ W
G : SimpleGraph V
v w : V
h : Adj G v w
⊢ Relation.Map G.Adj (↑f) (↑f) (↑f w) (↑f v)
[PROOFSTEP]
use w, v, h.symm, rfl
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a✝ b c u v w : V
e : Sym2 V
f : V ↪ W
G : SimpleGraph V
a : W
⊢ ¬Relation.Map G.Adj (↑f) (↑f) a a
[PROOFSTEP]
rintro ⟨v, w, h, rfl, h'⟩
[GOAL]
case intro.intro.intro.intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
f : V ↪ W
G : SimpleGraph V
v w : V
h : Adj G v w
h' : ↑f w = ↑f v
⊢ False
[PROOFSTEP]
exact h.ne (f.injective h'.symm)
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
f : V ↪ W
⊢ Monotone (SimpleGraph.map f)
[PROOFSTEP]
rintro G G' h _ _ ⟨u, v, ha, rfl, rfl⟩
[GOAL]
case intro.intro.intro.intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G'✝ : SimpleGraph W
a b c u✝ v✝ w : V
e : Sym2 V
f : V ↪ W
G G' : SimpleGraph V
h : G ≤ G'
u v : V
ha : Adj G u v
⊢ Adj (SimpleGraph.map f G') (↑f u) (↑f v)
[PROOFSTEP]
exact ⟨_, _, h ha, rfl, rfl⟩
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
f : V ↪ W
⊢ Monotone (SimpleGraph.comap ↑f)
[PROOFSTEP]
intro G G' h _ _ ha
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G'✝ : SimpleGraph W
a b c u v w : V
e : Sym2 V
f : V ↪ W
G G' : SimpleGraph W
h : G ≤ G'
v✝ w✝ : V
ha : Adj (SimpleGraph.comap (↑f) G) v✝ w✝
⊢ Adj (SimpleGraph.comap (↑f) G') v✝ w✝
[PROOFSTEP]
exact h ha
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
f : V ↪ W
G : SimpleGraph V
⊢ SimpleGraph.comap (↑f) (SimpleGraph.map f G) = G
[PROOFSTEP]
ext
[GOAL]
case Adj.h.h.a
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
f : V ↪ W
G : SimpleGraph V
x✝¹ x✝ : V
⊢ Adj (SimpleGraph.comap (↑f) (SimpleGraph.map f G)) x✝¹ x✝ ↔ Adj G x✝¹ x✝
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G'✝ : SimpleGraph W
a b c u v w : V
e : Sym2 V
f : V ↪ W
G : SimpleGraph V
G' : SimpleGraph W
⊢ G ≤ SimpleGraph.comap (↑f) G' → SimpleGraph.map f G ≤ G'
[PROOFSTEP]
rintro h _ _ ⟨u, v, ha, rfl, rfl⟩
[GOAL]
case intro.intro.intro.intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G'✝ : SimpleGraph W
a b c u✝ v✝ w : V
e : Sym2 V
f : V ↪ W
G : SimpleGraph V
G' : SimpleGraph W
h : G ≤ SimpleGraph.comap (↑f) G'
u v : V
ha : Adj G u v
⊢ Adj G' (↑f u) (↑f v)
[PROOFSTEP]
exact h ha
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
f : V ↪ W
G : SimpleGraph W
⊢ SimpleGraph.map f (SimpleGraph.comap (↑f) G) ≤ G
[PROOFSTEP]
rw [map_le_iff_le_comap]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
f : V → W
inst✝ : Subsingleton V
⊢ G ≤ SimpleGraph.comap f G'
[PROOFSTEP]
intros v w
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
f : V → W
inst✝ : Subsingleton V
v w : V
⊢ Adj G v w → Adj (SimpleGraph.comap f G') v w
[PROOFSTEP]
simp [Subsingleton.elim v w]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
f : V ↪ W
inst✝ : Subsingleton V
⊢ SimpleGraph.map f G ≤ G'
[PROOFSTEP]
rw [map_le_iff_le_comap]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
f : V ↪ W
inst✝ : Subsingleton V
⊢ G ≤ SimpleGraph.comap (↑f) G'
[PROOFSTEP]
apply le_comap_of_subsingleton
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
v : V
⊢ induce {v} G = ⊤
[PROOFSTEP]
rw [eq_top_iff]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
v : V
⊢ ⊤ ≤ induce {v} G
[PROOFSTEP]
apply le_comap_of_subsingleton
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝ : Fintype ↑(neighborSet G v)
⊢ ¬v ∈ neighborFinset G v
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝ : Fintype ↑(neighborSet G v)
⊢ 0 < degree G v ↔ ∃ w, Adj G v w
[PROOFSTEP]
simp only [degree, card_pos, Finset.Nonempty, mem_neighborFinset]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝² : Fintype ↑(neighborSet G v)
inst✝¹ : Fintype ↑(neighborSet Gᶜ v)
inst✝ : Fintype V
⊢ degree Gᶜ v = Fintype.card V - 1 - degree G v
[PROOFSTEP]
classical
rw [← card_neighborSet_union_compl_neighborSet G v, Set.toFinset_union]
simp [card_disjoint_union (Set.disjoint_toFinset.mpr (compl_neighborSet_disjoint G v))]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝² : Fintype ↑(neighborSet G v)
inst✝¹ : Fintype ↑(neighborSet Gᶜ v)
inst✝ : Fintype V
⊢ degree Gᶜ v = Fintype.card V - 1 - degree G v
[PROOFSTEP]
rw [← card_neighborSet_union_compl_neighborSet G v, Set.toFinset_union]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝² : Fintype ↑(neighborSet G v)
inst✝¹ : Fintype ↑(neighborSet Gᶜ v)
inst✝ : Fintype V
⊢ degree Gᶜ v = card (Set.toFinset (neighborSet G v) ∪ Set.toFinset (neighborSet Gᶜ v)) - degree G v
[PROOFSTEP]
simp [card_disjoint_union (Set.disjoint_toFinset.mpr (compl_neighborSet_disjoint G v))]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝¹ : Fintype ↑(neighborSet G v)
inst✝ : DecidableEq V
⊢ Fintype.card ↑(incidenceSet G v) = degree G v
[PROOFSTEP]
rw [Fintype.card_congr (G.incidenceSetEquivNeighborSet v)]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝¹ : Fintype ↑(neighborSet G v)
inst✝ : DecidableEq V
⊢ Fintype.card ↑(neighborSet G v) = degree G v
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝¹ : Fintype ↑(neighborSet G v)
inst✝ : DecidableEq V
⊢ card (incidenceFinset G v) = degree G v
[PROOFSTEP]
rw [← G.card_incidenceSet_eq_degree]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝¹ : Fintype ↑(neighborSet G v)
inst✝ : DecidableEq V
⊢ card (incidenceFinset G v) = Fintype.card ↑(incidenceSet G v)
[PROOFSTEP]
apply Set.toFinset_card
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝² : Fintype ↑(neighborSet G v)
inst✝¹ : DecidableEq V
inst✝ : Fintype ↑(edgeSet G)
⊢ incidenceFinset G v = filter (Membership.mem v) (edgeFinset G)
[PROOFSTEP]
ext e
[GOAL]
case a
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e✝ : Sym2 V
inst✝² : Fintype ↑(neighborSet G v)
inst✝¹ : DecidableEq V
inst✝ : Fintype ↑(edgeSet G)
e : Sym2 V
⊢ e ∈ incidenceFinset G v ↔ e ∈ filter (Membership.mem v) (edgeFinset G)
[PROOFSTEP]
refine' Sym2.ind (fun x y => _) e
[GOAL]
case a
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e✝ : Sym2 V
inst✝² : Fintype ↑(neighborSet G v)
inst✝¹ : DecidableEq V
inst✝ : Fintype ↑(edgeSet G)
e : Sym2 V
x y : V
⊢ Quotient.mk (Sym2.Rel.setoid V) (x, y) ∈ incidenceFinset G v ↔
    Quotient.mk (Sym2.Rel.setoid V) (x, y) ∈ filter (Membership.mem v) (edgeFinset G)
[PROOFSTEP]
simp [mk'_mem_incidenceSet_iff]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝³ : LocallyFinite G✝
inst✝² : Fintype V
inst✝¹ : DecidableEq V
G : SimpleGraph V
inst✝ : DecidableRel G.Adj
k : ℕ
h : IsRegularOfDegree G k
⊢ IsRegularOfDegree Gᶜ (Fintype.card V - 1 - k)
[PROOFSTEP]
intro v
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝³ : LocallyFinite G✝
inst✝² : Fintype V
inst✝¹ : DecidableEq V
G : SimpleGraph V
inst✝ : DecidableRel G.Adj
k : ℕ
h : IsRegularOfDegree G k
v : V
⊢ degree Gᶜ v = Fintype.card V - 1 - k
[PROOFSTEP]
rw [degree_compl, h v]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableRel G.Adj
v : V
⊢ DecidablePred fun x => x ∈ neighborSet G v
[PROOFSTEP]
simp_rw [mem_neighborSet]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableRel G.Adj
v : V
⊢ DecidablePred fun x => Adj G v x
[PROOFSTEP]
infer_instance
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝¹ : Fintype V
v : V
inst✝ : DecidableRel G.Adj
⊢ neighborFinset G v = filter (Adj G v) univ
[PROOFSTEP]
ext
[GOAL]
case a
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝¹ : Fintype V
v : V
inst✝ : DecidableRel G.Adj
a✝ : V
⊢ a✝ ∈ neighborFinset G v ↔ a✝ ∈ filter (Adj G v) univ
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝² : Fintype V
inst✝¹ : DecidableEq V
inst✝ : DecidableRel G.Adj
v : V
⊢ neighborFinset Gᶜ v = (neighborFinset G v)ᶜ \ {v}
[PROOFSTEP]
simp only [neighborFinset, neighborSet_compl, Set.toFinset_diff, Set.toFinset_compl, Set.toFinset_singleton]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableEq V
v : V
⊢ degree ⊤ v = Fintype.card V - 1
[PROOFSTEP]
erw [degree, neighborFinset_eq_filter, filter_ne, card_erase_of_mem (mem_univ v), card_univ]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝ : Fintype V
v : V
⊢ degree ⊥ v = 0
[PROOFSTEP]
erw [degree, neighborFinset_eq_filter, filter_False]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝ : Fintype V
v : V
⊢ card ∅ = 0
[PROOFSTEP]
exact Finset.card_empty
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableEq V
⊢ IsRegularOfDegree ⊤ (Fintype.card V - 1)
[PROOFSTEP]
intro v
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableEq V
v : V
⊢ degree ⊤ v = Fintype.card V - 1
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝² : Fintype V
inst✝¹ : DecidableRel G.Adj
inst✝ : Nonempty V
⊢ ∃ v, minDegree G = degree G v
[PROOFSTEP]
obtain ⟨t, ht : _ = _⟩ := min_of_nonempty (univ_nonempty.image fun v => G.degree v)
[GOAL]
case intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝² : Fintype V
inst✝¹ : DecidableRel G.Adj
inst✝ : Nonempty V
t : ℕ
ht : Finset.min (image (fun v => degree G v) univ) = ↑t
⊢ ∃ v, minDegree G = degree G v
[PROOFSTEP]
obtain ⟨v, _, rfl⟩ := mem_image.mp (mem_of_min ht)
[GOAL]
case intro.intro.intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝² : Fintype V
inst✝¹ : DecidableRel G.Adj
inst✝ : Nonempty V
v : V
left✝ : v ∈ univ
ht : Finset.min (image (fun v => degree G v) univ) = ↑(degree G v)
⊢ ∃ v, minDegree G = degree G v
[PROOFSTEP]
refine' ⟨v, by simp [minDegree, ht]⟩
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝² : Fintype V
inst✝¹ : DecidableRel G.Adj
inst✝ : Nonempty V
v : V
left✝ : v ∈ univ
ht : Finset.min (image (fun v => degree G v) univ) = ↑(degree G v)
⊢ minDegree G = degree G v
[PROOFSTEP]
simp [minDegree, ht]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableRel G.Adj
v : V
⊢ minDegree G ≤ degree G v
[PROOFSTEP]
obtain ⟨t, ht⟩ := Finset.min_of_mem (mem_image_of_mem (fun v => G.degree v) (mem_univ v))
[GOAL]
case intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableRel G.Adj
v : V
t : ℕ
ht : Finset.min (image (fun v => degree G v) univ) = ↑t
⊢ minDegree G ≤ degree G v
[PROOFSTEP]
have := Finset.min_le_of_eq (mem_image_of_mem _ (mem_univ v)) ht
[GOAL]
case intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableRel G.Adj
v : V
t : ℕ
ht : Finset.min (image (fun v => degree G v) univ) = ↑t
this : t ≤ degree G v
⊢ minDegree G ≤ degree G v
[PROOFSTEP]
rwa [minDegree, ht]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝² : Fintype V
inst✝¹ : DecidableRel G.Adj
inst✝ : Nonempty V
k : ℕ
h : ∀ (v : V), k ≤ degree G v
⊢ k ≤ minDegree G
[PROOFSTEP]
rcases G.exists_minimal_degree_vertex with ⟨v, hv⟩
[GOAL]
case intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝² : Fintype V
inst✝¹ : DecidableRel G.Adj
inst✝ : Nonempty V
k : ℕ
h : ∀ (v : V), k ≤ degree G v
v : V
hv : minDegree G = degree G v
⊢ k ≤ minDegree G
[PROOFSTEP]
rw [hv]
[GOAL]
case intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝² : Fintype V
inst✝¹ : DecidableRel G.Adj
inst✝ : Nonempty V
k : ℕ
h : ∀ (v : V), k ≤ degree G v
v : V
hv : minDegree G = degree G v
⊢ k ≤ degree G v
[PROOFSTEP]
apply h
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝² : Fintype V
inst✝¹ : DecidableRel G.Adj
inst✝ : Nonempty V
⊢ ∃ v, maxDegree G = degree G v
[PROOFSTEP]
obtain ⟨t, ht⟩ := max_of_nonempty (univ_nonempty.image fun v => G.degree v)
[GOAL]
case intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝² : Fintype V
inst✝¹ : DecidableRel G.Adj
inst✝ : Nonempty V
t : ℕ
ht : Finset.max (image (fun v => degree G v) univ) = ↑t
⊢ ∃ v, maxDegree G = degree G v
[PROOFSTEP]
have ht₂ := mem_of_max ht
[GOAL]
case intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝² : Fintype V
inst✝¹ : DecidableRel G.Adj
inst✝ : Nonempty V
t : ℕ
ht : Finset.max (image (fun v => degree G v) univ) = ↑t
ht₂ : t ∈ image (fun v => degree G v) univ
⊢ ∃ v, maxDegree G = degree G v
[PROOFSTEP]
simp only [mem_image, mem_univ, exists_prop_of_true] at ht₂ 
[GOAL]
case intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝² : Fintype V
inst✝¹ : DecidableRel G.Adj
inst✝ : Nonempty V
t : ℕ
ht : Finset.max (image (fun v => degree G v) univ) = ↑t
ht₂ : ∃ a, True ∧ degree G a = t
⊢ ∃ v, maxDegree G = degree G v
[PROOFSTEP]
rcases ht₂ with ⟨v, _, rfl⟩
[GOAL]
case intro.intro.intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝² : Fintype V
inst✝¹ : DecidableRel G.Adj
inst✝ : Nonempty V
v : V
left✝ : True
ht : Finset.max (image (fun v => degree G v) univ) = ↑(degree G v)
⊢ ∃ v, maxDegree G = degree G v
[PROOFSTEP]
refine' ⟨v, _⟩
[GOAL]
case intro.intro.intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝² : Fintype V
inst✝¹ : DecidableRel G.Adj
inst✝ : Nonempty V
v : V
left✝ : True
ht : Finset.max (image (fun v => degree G v) univ) = ↑(degree G v)
⊢ maxDegree G = degree G v
[PROOFSTEP]
rw [maxDegree, ht]
[GOAL]
case intro.intro.intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝² : Fintype V
inst✝¹ : DecidableRel G.Adj
inst✝ : Nonempty V
v : V
left✝ : True
ht : Finset.max (image (fun v => degree G v) univ) = ↑(degree G v)
⊢ Option.getD (↑(degree G v)) 0 = degree G v
[PROOFSTEP]
rfl
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableRel G.Adj
v : V
⊢ degree G v ≤ maxDegree G
[PROOFSTEP]
obtain ⟨t, ht : _ = _⟩ := Finset.max_of_mem (mem_image_of_mem (fun v => G.degree v) (mem_univ v))
[GOAL]
case intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableRel G.Adj
v : V
t : ℕ
ht : Finset.max (image (fun v => degree G v) univ) = ↑t
⊢ degree G v ≤ maxDegree G
[PROOFSTEP]
have := Finset.le_max_of_eq (mem_image_of_mem _ (mem_univ v)) ht
[GOAL]
case intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableRel G.Adj
v : V
t : ℕ
ht : Finset.max (image (fun v => degree G v) univ) = ↑t
this : degree G v ≤ t
⊢ degree G v ≤ maxDegree G
[PROOFSTEP]
rwa [maxDegree, ht]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableRel G.Adj
k : ℕ
h : ∀ (v : V), degree G v ≤ k
⊢ maxDegree G ≤ k
[PROOFSTEP]
by_cases hV : (univ : Finset V).Nonempty
[GOAL]
case pos
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableRel G.Adj
k : ℕ
h : ∀ (v : V), degree G v ≤ k
hV : Finset.Nonempty univ
⊢ maxDegree G ≤ k
[PROOFSTEP]
haveI : Nonempty V := univ_nonempty_iff.mp hV
[GOAL]
case pos
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableRel G.Adj
k : ℕ
h : ∀ (v : V), degree G v ≤ k
hV : Finset.Nonempty univ
this : Nonempty V
⊢ maxDegree G ≤ k
[PROOFSTEP]
obtain ⟨v, hv⟩ := G.exists_maximal_degree_vertex
[GOAL]
case pos.intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableRel G.Adj
k : ℕ
h : ∀ (v : V), degree G v ≤ k
hV : Finset.Nonempty univ
this : Nonempty V
v : V
hv : maxDegree G = degree G v
⊢ maxDegree G ≤ k
[PROOFSTEP]
rw [hv]
[GOAL]
case pos.intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableRel G.Adj
k : ℕ
h : ∀ (v : V), degree G v ≤ k
hV : Finset.Nonempty univ
this : Nonempty V
v : V
hv : maxDegree G = degree G v
⊢ degree G v ≤ k
[PROOFSTEP]
apply h
[GOAL]
case neg
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableRel G.Adj
k : ℕ
h : ∀ (v : V), degree G v ≤ k
hV : ¬Finset.Nonempty univ
⊢ maxDegree G ≤ k
[PROOFSTEP]
rw [not_nonempty_iff_eq_empty] at hV 
[GOAL]
case neg
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableRel G.Adj
k : ℕ
h : ∀ (v : V), degree G v ≤ k
hV : univ = ∅
⊢ maxDegree G ≤ k
[PROOFSTEP]
rw [maxDegree, hV, image_empty]
[GOAL]
case neg
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableRel G.Adj
k : ℕ
h : ∀ (v : V), degree G v ≤ k
hV : univ = ∅
⊢ Option.getD (Finset.max ∅) 0 ≤ k
[PROOFSTEP]
exact zero_le k
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableRel G.Adj
v : V
⊢ degree G v < Fintype.card V
[PROOFSTEP]
classical
apply Finset.card_lt_card
rw [Finset.ssubset_iff]
exact ⟨v, by simp, Finset.subset_univ _⟩
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableRel G.Adj
v : V
⊢ degree G v < Fintype.card V
[PROOFSTEP]
apply Finset.card_lt_card
[GOAL]
case h
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableRel G.Adj
v : V
⊢ neighborFinset G v ⊂ univ
[PROOFSTEP]
rw [Finset.ssubset_iff]
[GOAL]
case h
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableRel G.Adj
v : V
⊢ ∃ a x, insert a (neighborFinset G v) ⊆ univ
[PROOFSTEP]
exact ⟨v, by simp, Finset.subset_univ _⟩
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableRel G.Adj
v : V
⊢ ¬v ∈ neighborFinset G v
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
inst✝² : Fintype V
inst✝¹ : DecidableRel G.Adj
inst✝ : Nonempty V
⊢ maxDegree G < Fintype.card V
[PROOFSTEP]
cases' G.exists_maximal_degree_vertex with v hv
[GOAL]
case intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝² : Fintype V
inst✝¹ : DecidableRel G.Adj
inst✝ : Nonempty V
v : V
hv : maxDegree G = degree G v
⊢ maxDegree G < Fintype.card V
[PROOFSTEP]
rw [hv]
[GOAL]
case intro
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
inst✝² : Fintype V
inst✝¹ : DecidableRel G.Adj
inst✝ : Nonempty V
v : V
hv : maxDegree G = degree G v
⊢ degree G v < Fintype.card V
[PROOFSTEP]
apply G.degree_lt_card_verts v
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableRel G.Adj
v w : V
⊢ Fintype.card ↑(commonNeighbors G v w) ≤ degree G v
[PROOFSTEP]
rw [← card_neighborSet_eq_degree]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableRel G.Adj
v w : V
⊢ Fintype.card ↑(commonNeighbors G v w) ≤ Fintype.card ↑(neighborSet G v)
[PROOFSTEP]
exact Set.card_le_of_subset (Set.inter_subset_left _ _)
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableRel G.Adj
v w : V
⊢ Fintype.card ↑(commonNeighbors G v w) ≤ degree G w
[PROOFSTEP]
simp_rw [commonNeighbors_symm _ v w, card_commonNeighbors_le_degree_left]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
inst✝¹ : Fintype V
G : SimpleGraph V
inst✝ : DecidableRel G.Adj
v w : V
h : Adj G v w
⊢ Fintype.card ↑(commonNeighbors G v w) < degree G v
[PROOFSTEP]
classical
erw [← Set.toFinset_card]
apply Finset.card_lt_card
rw [Finset.ssubset_iff]
use w
constructor
· rw [Finset.insert_subset_iff]
  constructor
  · simpa
  · rw [neighborFinset, Set.toFinset_subset_toFinset]
    exact G.commonNeighbors_subset_neighborSet_left _ _
· rw [Set.mem_toFinset]
  apply not_mem_commonNeighbors_right
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
inst✝¹ : Fintype V
G : SimpleGraph V
inst✝ : DecidableRel G.Adj
v w : V
h : Adj G v w
⊢ Fintype.card ↑(commonNeighbors G v w) < degree G v
[PROOFSTEP]
erw [← Set.toFinset_card]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
inst✝¹ : Fintype V
G : SimpleGraph V
inst✝ : DecidableRel G.Adj
v w : V
h : Adj G v w
⊢ card (Set.toFinset (commonNeighbors G v w)) < degree G v
[PROOFSTEP]
apply Finset.card_lt_card
[GOAL]
case h
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
inst✝¹ : Fintype V
G : SimpleGraph V
inst✝ : DecidableRel G.Adj
v w : V
h : Adj G v w
⊢ Set.toFinset (commonNeighbors G v w) ⊂ neighborFinset G v
[PROOFSTEP]
rw [Finset.ssubset_iff]
[GOAL]
case h
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
inst✝¹ : Fintype V
G : SimpleGraph V
inst✝ : DecidableRel G.Adj
v w : V
h : Adj G v w
⊢ ∃ a x, insert a (Set.toFinset (commonNeighbors G v w)) ⊆ neighborFinset G v
[PROOFSTEP]
use w
[GOAL]
case h
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
inst✝¹ : Fintype V
G : SimpleGraph V
inst✝ : DecidableRel G.Adj
v w : V
h : Adj G v w
⊢ ∃ x, insert w (Set.toFinset (commonNeighbors G v w)) ⊆ neighborFinset G v
[PROOFSTEP]
constructor
[GOAL]
case h.h
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
inst✝¹ : Fintype V
G : SimpleGraph V
inst✝ : DecidableRel G.Adj
v w : V
h : Adj G v w
⊢ insert w (Set.toFinset (commonNeighbors G v w)) ⊆ neighborFinset G v
[PROOFSTEP]
rw [Finset.insert_subset_iff]
[GOAL]
case h.h
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
inst✝¹ : Fintype V
G : SimpleGraph V
inst✝ : DecidableRel G.Adj
v w : V
h : Adj G v w
⊢ w ∈ neighborFinset G v ∧ Set.toFinset (commonNeighbors G v w) ⊆ neighborFinset G v
[PROOFSTEP]
constructor
[GOAL]
case h.h.left
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
inst✝¹ : Fintype V
G : SimpleGraph V
inst✝ : DecidableRel G.Adj
v w : V
h : Adj G v w
⊢ w ∈ neighborFinset G v
[PROOFSTEP]
simpa
[GOAL]
case h.h.right
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
inst✝¹ : Fintype V
G : SimpleGraph V
inst✝ : DecidableRel G.Adj
v w : V
h : Adj G v w
⊢ Set.toFinset (commonNeighbors G v w) ⊆ neighborFinset G v
[PROOFSTEP]
rw [neighborFinset, Set.toFinset_subset_toFinset]
[GOAL]
case h.h.right
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
inst✝¹ : Fintype V
G : SimpleGraph V
inst✝ : DecidableRel G.Adj
v w : V
h : Adj G v w
⊢ commonNeighbors G v w ⊆ neighborSet G v
[PROOFSTEP]
exact G.commonNeighbors_subset_neighborSet_left _ _
[GOAL]
case h.w
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
inst✝¹ : Fintype V
G : SimpleGraph V
inst✝ : DecidableRel G.Adj
v w : V
h : Adj G v w
⊢ ¬w ∈ Set.toFinset (commonNeighbors G v w)
[PROOFSTEP]
rw [Set.mem_toFinset]
[GOAL]
case h.w
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
inst✝¹ : Fintype V
G : SimpleGraph V
inst✝ : DecidableRel G.Adj
v w : V
h : Adj G v w
⊢ ¬w ∈ commonNeighbors G v w
[PROOFSTEP]
apply not_mem_commonNeighbors_right
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableEq V
v w : V
h : v ≠ w
⊢ Fintype.card ↑(commonNeighbors ⊤ v w) = Fintype.card V - 2
[PROOFSTEP]
simp only [commonNeighbors_top_eq, ← Set.toFinset_card, Set.toFinset_diff]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableEq V
v w : V
h : v ≠ w
⊢ card (Set.toFinset Set.univ \ Set.toFinset {v, w}) = Fintype.card V - 2
[PROOFSTEP]
rw [Finset.card_sdiff]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableEq V
v w : V
h : v ≠ w
⊢ card (Set.toFinset Set.univ) - card (Set.toFinset {v, w}) = Fintype.card V - 2
[PROOFSTEP]
simp [Finset.card_univ, h]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
inst✝¹ : Fintype V
inst✝ : DecidableEq V
v w : V
h : v ≠ w
⊢ Set.toFinset {v, w} ⊆ Set.toFinset Set.univ
[PROOFSTEP]
simp only [Set.toFinset_subset_toFinset, Set.subset_univ]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
f : G →g G'
hinj : Injective ↑f
⊢ Injective (mapEdgeSet f)
[PROOFSTEP]
rintro ⟨e₁, h₁⟩ ⟨e₂, h₂⟩
[GOAL]
case mk.mk
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
f : G →g G'
hinj : Injective ↑f
e₁ : Sym2 V
h₁ : e₁ ∈ edgeSet G
e₂ : Sym2 V
h₂ : e₂ ∈ edgeSet G
⊢ mapEdgeSet f { val := e₁, property := h₁ } = mapEdgeSet f { val := e₂, property := h₂ } →
    { val := e₁, property := h₁ } = { val := e₂, property := h₂ }
[PROOFSTEP]
dsimp [Hom.mapEdgeSet]
[GOAL]
case mk.mk
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
f : G →g G'
hinj : Injective ↑f
e₁ : Sym2 V
h₁ : e₁ ∈ edgeSet G
e₂ : Sym2 V
h₂ : e₂ ∈ edgeSet G
⊢ { val := Sym2.map (↑f) e₁, property := (_ : Sym2.map ↑f ↑{ val := e₁, property := h₁ } ∈ edgeSet G') } =
      { val := Sym2.map (↑f) e₂, property := (_ : Sym2.map ↑f ↑{ val := e₂, property := h₂ } ∈ edgeSet G') } →
    { val := e₁, property := h₁ } = { val := e₂, property := h₂ }
[PROOFSTEP]
repeat' rw [Subtype.mk_eq_mk]
[GOAL]
case mk.mk
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
f : G →g G'
hinj : Injective ↑f
e₁ : Sym2 V
h₁ : e₁ ∈ edgeSet G
e₂ : Sym2 V
h₂ : e₂ ∈ edgeSet G
⊢ { val := Sym2.map (↑f) e₁, property := (_ : Sym2.map ↑f ↑{ val := e₁, property := h₁ } ∈ edgeSet G') } =
      { val := Sym2.map (↑f) e₂, property := (_ : Sym2.map ↑f ↑{ val := e₂, property := h₂ } ∈ edgeSet G') } →
    { val := e₁, property := h₁ } = { val := e₂, property := h₂ }
[PROOFSTEP]
rw [Subtype.mk_eq_mk]
[GOAL]
case mk.mk
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
f : G →g G'
hinj : Injective ↑f
e₁ : Sym2 V
h₁ : e₁ ∈ edgeSet G
e₂ : Sym2 V
h₂ : e₂ ∈ edgeSet G
⊢ Sym2.map (↑f) e₁ = Sym2.map (↑f) e₂ → { val := e₁, property := h₁ } = { val := e₂, property := h₂ }
[PROOFSTEP]
rw [Subtype.mk_eq_mk]
[GOAL]
case mk.mk
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
f : G →g G'
hinj : Injective ↑f
e₁ : Sym2 V
h₁ : e₁ ∈ edgeSet G
e₂ : Sym2 V
h₂ : e₂ ∈ edgeSet G
⊢ Sym2.map (↑f) e₁ = Sym2.map (↑f) e₂ → e₁ = e₂
[PROOFSTEP]
rw [Subtype.mk_eq_mk]
[GOAL]
case mk.mk
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
f : G →g G'
hinj : Injective ↑f
e₁ : Sym2 V
h₁ : e₁ ∈ edgeSet G
e₂ : Sym2 V
h₂ : e₂ ∈ edgeSet G
⊢ Sym2.map (↑f) e₁ = Sym2.map (↑f) e₂ → e₁ = e₂
[PROOFSTEP]
apply Sym2.map.injective hinj
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
f✝ : G →g G'
f : ⊤ →g G'
⊢ Injective ↑f
[PROOFSTEP]
intro v w h
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
f✝ : G →g G'
f : ⊤ →g G'
v w : V
h : ↑f v = ↑f w
⊢ v = w
[PROOFSTEP]
contrapose! h
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
f✝ : G →g G'
f : ⊤ →g G'
v w : V
h : v ≠ w
⊢ ↑f v ≠ ↑f w
[PROOFSTEP]
exact G'.ne_of_adj (map_adj _ ((top_adj _ _).mpr h))
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
f✝ : G✝ →g G'
f : V → W
G : SimpleGraph W
⊢ ∀ {a b : V}, Adj (SimpleGraph.comap f G) a b → Adj G (f a) (f b)
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
f : G ↪g G'
v : V
⊢ Injective fun w => { val := ↑f ↑w, property := (_ : ↑f ↑w ∈ neighborSet G' (↑f v)) }
[PROOFSTEP]
rintro ⟨w₁, h₁⟩ ⟨w₂, h₂⟩ h
[GOAL]
case mk.mk
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
f : G ↪g G'
v w₁ : V
h₁ : w₁ ∈ neighborSet G v
w₂ : V
h₂ : w₂ ∈ neighborSet G v
h :
  (fun w => { val := ↑f ↑w, property := (_ : ↑f ↑w ∈ neighborSet G' (↑f v)) }) { val := w₁, property := h₁ } =
    (fun w => { val := ↑f ↑w, property := (_ : ↑f ↑w ∈ neighborSet G' (↑f v)) }) { val := w₂, property := h₂ }
⊢ { val := w₁, property := h₁ } = { val := w₂, property := h₂ }
[PROOFSTEP]
rw [Subtype.mk_eq_mk] at h ⊢
[GOAL]
case mk.mk
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w : V
e : Sym2 V
f : G ↪g G'
v w₁ : V
h₁ : w₁ ∈ neighborSet G v
w₂ : V
h₂ : w₂ ∈ neighborSet G v
h : ↑f ↑{ val := w₁, property := h₁ } = ↑f ↑{ val := w₂, property := h₂ }
⊢ w₁ = w₂
[PROOFSTEP]
exact f.inj' h
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
f✝ : G✝ ↪g G'
f : V ↪ W
G : SimpleGraph W
⊢ ∀ {a b : V},
    Adj G (↑{ toFun := f.toFun, inj' := (_ : Injective f.toFun) } a)
        (↑{ toFun := f.toFun, inj' := (_ : Injective f.toFun) } b) ↔
      Adj (SimpleGraph.comap (↑f) G) a b
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
f✝ : G✝ ↪g G'
f : V ↪ W
G : SimpleGraph V
⊢ ∀ {a b : V},
    Adj (SimpleGraph.map f G) (↑{ toFun := f.toFun, inj' := (_ : Injective f.toFun) } a)
        (↑{ toFun := f.toFun, inj' := (_ : Injective f.toFun) } b) ↔
      Adj G a b
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
f✝ : G ↪g G'
α : Type u_3
β : Type u_4
f : α ↪ β
⊢ ∀ {a b : α},
    Adj ⊤ (↑{ toFun := f.toFun, inj' := (_ : Injective f.toFun) } a)
        (↑{ toFun := f.toFun, inj' := (_ : Injective f.toFun) } b) ↔
      Adj ⊤ a b
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G'' : SimpleGraph X
s✝ : Set V
t : Set W
r : Set X
φ : G✝ →g G'
φst : Set.MapsTo (↑φ) s✝ t
ψ : G' →g G''
ψtr : Set.MapsTo (↑ψ) t r
G : SimpleGraph V
s : Set V
⊢ induceHom Hom.id (_ : Set.MapsTo id s s) = Hom.id
[PROOFSTEP]
ext x
[GOAL]
case h.a
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G'' : SimpleGraph X
s✝ : Set V
t : Set W
r : Set X
φ : G✝ →g G'
φst : Set.MapsTo (↑φ) s✝ t
ψ : G' →g G''
ψtr : Set.MapsTo (↑ψ) t r
G : SimpleGraph V
s : Set V
x : ↑s
⊢ ↑(↑(induceHom Hom.id (_ : Set.MapsTo id s s)) x) = ↑(↑Hom.id x)
[PROOFSTEP]
rfl
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G'' : SimpleGraph X
s : Set V
t : Set W
r : Set X
φ : G →g G'
φst : Set.MapsTo (↑φ) s t
ψ : G' →g G''
ψtr : Set.MapsTo (↑ψ) t r
⊢ Hom.comp (induceHom ψ ψtr) (induceHom φ φst) = induceHom (Hom.comp ψ φ) (_ : Set.MapsTo (↑ψ ∘ fun x => ↑φ x) s r)
[PROOFSTEP]
ext x
[GOAL]
case h.a
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G'' : SimpleGraph X
s : Set V
t : Set W
r : Set X
φ : G →g G'
φst : Set.MapsTo (↑φ) s t
ψ : G' →g G''
ψtr : Set.MapsTo (↑ψ) t r
x : ↑s
⊢ ↑(↑(Hom.comp (induceHom ψ ψtr) (induceHom φ φst)) x) =
    ↑(↑(induceHom (Hom.comp ψ φ) (_ : Set.MapsTo (↑ψ ∘ fun x => ↑φ x) s r)) x)
[PROOFSTEP]
rfl
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G'' : SimpleGraph X
s : Set V
t : Set W
r : Set X
φ : G →g G'
φst : Set.MapsTo (↑φ) s t
ψ : G' →g G''
ψtr : Set.MapsTo (↑ψ) t r
hi : Set.InjOn (↑φ) s
⊢ Injective ↑(induceHom φ φst)
[PROOFSTEP]
erw [Set.MapsTo.restrict_inj]
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G'' : SimpleGraph X
s : Set V
t : Set W
r : Set X
φ : G →g G'
φst : Set.MapsTo (↑φ) s t
ψ : G' →g G''
ψtr : Set.MapsTo (↑ψ) t r
hi : Set.InjOn (↑φ) s
⊢ Set.InjOn (↑φ) s
[PROOFSTEP]
assumption
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G'' : SimpleGraph X
s : Set V
t : Set W
r : Set X
φ : G →g G'
φst : Set.MapsTo (↑φ) s t
ψ : G' →g G''
ψtr : Set.MapsTo (↑ψ) t r
hi : Set.InjOn (↑φ) s
⊢ Set.MapsTo (↑φ) s t
[PROOFSTEP]
assumption
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
s s' : Set V
h✝ h : s ≤ s'
⊢ ∀ {a b : ↑s},
    Adj (induce s' G) (↑(Set.embeddingOfSubset s s' h) a) (↑(Set.embeddingOfSubset s s' h) b) ↔ Adj (induce s G) a b
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
s s' : Set V
h : s ≤ s'
⊢ Embedding.toHom (induceHomOfLE G h) = induceHom Hom.id (_ : Set.MapsTo id s s')
[PROOFSTEP]
ext
[GOAL]
case h.a
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
s s' : Set V
h : s ≤ s'
x✝ : ↑s
⊢ ↑(↑(Embedding.toHom (induceHomOfLE G h)) x✝) = ↑(↑(induceHom Hom.id (_ : Set.MapsTo id s s')) x✝)
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
f : G ≃g G'
⊢ LeftInverse (Hom.mapEdgeSet (RelEmbedding.toRelHom (RelIso.toRelEmbedding (symm f))))
    (Hom.mapEdgeSet (RelEmbedding.toRelHom (RelIso.toRelEmbedding f)))
[PROOFSTEP]
rintro ⟨e, h⟩
[GOAL]
case mk
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e✝ : Sym2 V
f : G ≃g G'
e : Sym2 V
h : e ∈ edgeSet G
⊢ Hom.mapEdgeSet (RelEmbedding.toRelHom (RelIso.toRelEmbedding (symm f)))
      (Hom.mapEdgeSet (RelEmbedding.toRelHom (RelIso.toRelEmbedding f)) { val := e, property := h }) =
    { val := e, property := h }
[PROOFSTEP]
simp [Hom.mapEdgeSet, Sym2.map_map, RelEmbedding.toRelHom]
[GOAL]
case mk
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e✝ : Sym2 V
f : G ≃g G'
e : Sym2 V
h : e ∈ edgeSet G
⊢ Sym2.map
      (fun x =>
        ↑{ toFun := ↑(symm f), map_rel' := (_ : ∀ {a b : W}, Adj G' a b → Adj G (↑(symm f) a) (↑(symm f) b)) }
          (↑{ toFun := ↑f, map_rel' := (_ : ∀ {a b : V}, Adj G a b → Adj G' (↑f a) (↑f b)) } x))
      e =
    e
[PROOFSTEP]
convert congr_fun Sym2.map_id e
[GOAL]
case h.e'_2.h
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e✝ : Sym2 V
f : G ≃g G'
e : Sym2 V
h : e ∈ edgeSet G
x✝ : V
a✝ : x✝ ∈ e
⊢ ↑{ toFun := ↑(symm f), map_rel' := (_ : ∀ {a b : W}, Adj G' a b → Adj G (↑(symm f) a) (↑(symm f) b)) }
      (↑{ toFun := ↑f, map_rel' := (_ : ∀ {a b : V}, Adj G a b → Adj G' (↑f a) (↑f b)) } x✝) =
    id x✝
[PROOFSTEP]
exact RelIso.symm_apply_apply _ _
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
f : G ≃g G'
⊢ Function.RightInverse (Hom.mapEdgeSet (RelEmbedding.toRelHom (RelIso.toRelEmbedding (symm f))))
    (Hom.mapEdgeSet (RelEmbedding.toRelHom (RelIso.toRelEmbedding f)))
[PROOFSTEP]
rintro ⟨e, h⟩
[GOAL]
case mk
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e✝ : Sym2 V
f : G ≃g G'
e : Sym2 W
h : e ∈ edgeSet G'
⊢ Hom.mapEdgeSet (RelEmbedding.toRelHom (RelIso.toRelEmbedding f))
      (Hom.mapEdgeSet (RelEmbedding.toRelHom (RelIso.toRelEmbedding (symm f))) { val := e, property := h }) =
    { val := e, property := h }
[PROOFSTEP]
simp [Hom.mapEdgeSet, Sym2.map_map, RelEmbedding.toRelHom]
[GOAL]
case mk
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e✝ : Sym2 V
f : G ≃g G'
e : Sym2 W
h : e ∈ edgeSet G'
⊢ Sym2.map
      (fun x =>
        ↑{ toFun := ↑f, map_rel' := (_ : ∀ {a b : V}, Adj G a b → Adj G' (↑f a) (↑f b)) }
          (↑{ toFun := ↑(symm f), map_rel' := (_ : ∀ {a b : W}, Adj G' a b → Adj G (↑(symm f) a) (↑(symm f) b)) } x))
      e =
    e
[PROOFSTEP]
convert congr_fun Sym2.map_id e
[GOAL]
case h.e'_2.h
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e✝ : Sym2 V
f : G ≃g G'
e : Sym2 W
h : e ∈ edgeSet G'
x✝ : W
a✝ : x✝ ∈ e
⊢ ↑{ toFun := ↑f, map_rel' := (_ : ∀ {a b : V}, Adj G a b → Adj G' (↑f a) (↑f b)) }
      (↑{ toFun := ↑(symm f), map_rel' := (_ : ∀ {a b : W}, Adj G' a b → Adj G (↑(symm f) a) (↑(symm f) b)) } x✝) =
    id x✝
[PROOFSTEP]
exact RelIso.apply_symm_apply _ _
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
f : G ≃g G'
v : V
w : ↑(neighborSet G' (↑f v))
⊢ ↑(symm f) ↑w ∈ neighborSet G v
[PROOFSTEP]
simpa [RelIso.symm_apply_apply] using f.symm.apply_mem_neighborSet_iff.mpr w.2
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
f : G ≃g G'
v : V
w : ↑(neighborSet G v)
⊢ (fun w => { val := ↑(symm f) ↑w, property := (_ : ↑(symm f) ↑w ∈ neighborSet G v) })
      ((fun w => { val := ↑f ↑w, property := (_ : ↑f ↑w ∈ neighborSet G' (↑f v)) }) w) =
    w
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v✝ w✝ : V
e : Sym2 V
f : G ≃g G'
v : V
w : ↑(neighborSet G' (↑f v))
⊢ (fun w => { val := ↑f ↑w, property := (_ : ↑f ↑w ∈ neighborSet G' (↑f v)) })
      ((fun w => { val := ↑(symm f) ↑w, property := (_ : ↑(symm f) ↑w ∈ neighborSet G v) }) w) =
    w
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
f✝ : G ≃g G'
inst✝¹ : Fintype V
inst✝ : Fintype W
f : G ≃g G'
⊢ Fintype.card V = Fintype.card W
[PROOFSTEP]
rw [← Fintype.ofEquiv_card f.toEquiv]
  -- porting note: need to help it to find the typeclass instances from the target expression
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
f✝ : G ≃g G'
inst✝¹ : Fintype V
inst✝ : Fintype W
f : G ≃g G'
⊢ Fintype.card W = Fintype.card W
[PROOFSTEP]
apply @Fintype.card_congr' _ _ (_) (_) rfl
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
f✝ : G✝ ≃g G'
f : V ≃ W
G : SimpleGraph W
⊢ ∀ {a b : V},
    Adj G
        (↑{ toFun := f.toFun, invFun := f.invFun, left_inv := (_ : LeftInverse f.invFun f.toFun),
              right_inv := (_ : Function.RightInverse f.invFun f.toFun) }
          a)
        (↑{ toFun := f.toFun, invFun := f.invFun, left_inv := (_ : LeftInverse f.invFun f.toFun),
              right_inv := (_ : Function.RightInverse f.invFun f.toFun) }
          b) ↔
      Adj (SimpleGraph.comap (↑(Equiv.toEmbedding f)) G) a b
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
f✝ : G✝ ≃g G'
f : V ≃ W
G : SimpleGraph V
⊢ ∀ {a b : V},
    Adj (SimpleGraph.map (Equiv.toEmbedding f) G)
        (↑{ toFun := f.toFun, invFun := f.invFun, left_inv := (_ : LeftInverse f.invFun f.toFun),
              right_inv := (_ : Function.RightInverse f.invFun f.toFun) }
          a)
        (↑{ toFun := f.toFun, invFun := f.invFun, left_inv := (_ : LeftInverse f.invFun f.toFun),
              right_inv := (_ : Function.RightInverse f.invFun f.toFun) }
          b) ↔
      Adj G a b
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
f✝ : G ≃g G'
α : Type u_3
β : Type u_4
f : α ≃ β
⊢ ∀ {a b : α},
    Adj ⊤
        (↑{ toFun := f.toFun, invFun := f.invFun, left_inv := (_ : LeftInverse f.invFun f.toFun),
              right_inv := (_ : Function.RightInverse f.invFun f.toFun) }
          a)
        (↑{ toFun := f.toFun, invFun := f.invFun, left_inv := (_ : LeftInverse f.invFun f.toFun),
              right_inv := (_ : Function.RightInverse f.invFun f.toFun) }
          b) ↔
      Adj ⊤ a b
[PROOFSTEP]
simp
[GOAL]
ι : Sort u_1
𝕜 : Type u_2
V : Type u
W : Type v
X : Type w
G✝ : SimpleGraph V
G' : SimpleGraph W
a b c u v w : V
e : Sym2 V
G : SimpleGraph V
⊢ ∀ {a b : ↑Set.univ}, Adj G (↑(Equiv.Set.univ V) a) (↑(Equiv.Set.univ V) b) ↔ Adj (induce Set.univ G) a b
[PROOFSTEP]
simp only [Equiv.Set.univ, Equiv.coe_fn_mk, comap_Adj, Embedding.coe_subtype, Subtype.forall, Set.mem_univ,
  forall_true_left, implies_true]
