Theorem fusgreghash2wspv 41498

Description: According to statement 7 in [Huneke] p. 2: "For each vertex v, there are exactly ( k 2 ) paths with length two having v in the middle, ..." in a finite k-regular graph. For simple paths of length 2 represented by length 3 strings, we have again k*(k-1) such paths. (Contributed by Alexander van der Vekens, 10-Mar-2018.) (Revised by AV, 17-May-2021.)

Hypotheses

Ref	Expression
frgrhash2wsp.v	⊢ 𝑉 = (Vtx‘𝐺)
fusgreg2wsp.m	⊢ 𝑀 = (𝑎 ∈ 𝑉 ↦ {𝑤 ∈ (2 WSPathsN 𝐺) ∣ (𝑤‘1) = 𝑎})

Assertion

Ref	Expression
fusgreghash2wspv	⊢ (𝐺 ∈ FinUSGraph → ∀𝑣 ∈ 𝑉 (((VtxDeg‘𝐺)‘𝑣) = 𝐾 → (#‘(𝑀‘𝑣)) = (𝐾 · (𝐾 − 1))))

Distinct variable groups:   𝐺,𝑎   𝑉,𝑎   𝑤,𝐺,𝑎   𝑤,𝑉   𝑣,𝐺,𝑎,𝑤

Allowed substitution hints:   𝐾(𝑤,𝑣,𝑎)   𝑀(𝑤,𝑣,𝑎)   𝑉(𝑣)

Proof of Theorem fusgreghash2wspv

Dummy variables 𝑐 𝑑 are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		frgrhash2wsp.v	. . . . . . . 8 ⊢ 𝑉 = (Vtx‘𝐺)
2		fusgreg2wsp.m	. . . . . . . 8 ⊢ 𝑀 = (𝑎 ∈ 𝑉 ↦ {𝑤 ∈ (2 WSPathsN 𝐺) ∣ (𝑤‘1) = 𝑎})
3	1, 2	fusgr2wsp2nb 41497	. . . . . . 7 ⊢ ((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) → (𝑀‘𝑣) = ∪ 𝑐 ∈ (𝐺 NeighbVtx 𝑣)∪ 𝑑 ∈ ((𝐺 NeighbVtx 𝑣) ∖ {𝑐}){⟨“𝑐𝑣𝑑”⟩})
4	3	fveq2d 6089	. . . . . 6 ⊢ ((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) → (#‘(𝑀‘𝑣)) = (#‘∪ 𝑐 ∈ (𝐺 NeighbVtx 𝑣)∪ 𝑑 ∈ ((𝐺 NeighbVtx 𝑣) ∖ {𝑐}){⟨“𝑐𝑣𝑑”⟩}))
5	1	eleq2i 2676	. . . . . . . 8 ⊢ (𝑣 ∈ 𝑉 ↔ 𝑣 ∈ (Vtx‘𝐺))
6		nbfiusgrfi 40602	. . . . . . . 8 ⊢ ((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ (Vtx‘𝐺)) → (𝐺 NeighbVtx 𝑣) ∈ Fin)
7	5, 6	sylan2b 490	. . . . . . 7 ⊢ ((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) → (𝐺 NeighbVtx 𝑣) ∈ Fin)
8	7	adantr 479	. . . . . . . . 9 ⊢ (((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ 𝑐 ∈ (𝐺 NeighbVtx 𝑣)) → (𝐺 NeighbVtx 𝑣) ∈ Fin)
9		diffi 8051	. . . . . . . . 9 ⊢ ((𝐺 NeighbVtx 𝑣) ∈ Fin → ((𝐺 NeighbVtx 𝑣) ∖ {𝑐}) ∈ Fin)
10	8, 9	syl 17	. . . . . . . 8 ⊢ (((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ 𝑐 ∈ (𝐺 NeighbVtx 𝑣)) → ((𝐺 NeighbVtx 𝑣) ∖ {𝑐}) ∈ Fin)
11		snfi 7897	. . . . . . . . . 10 ⊢ {⟨“𝑐𝑣𝑑”⟩} ∈ Fin
12	11	a1i 11	. . . . . . . . 9 ⊢ ((((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ 𝑐 ∈ (𝐺 NeighbVtx 𝑣)) ∧ 𝑑 ∈ ((𝐺 NeighbVtx 𝑣) ∖ {𝑐})) → {⟨“𝑐𝑣𝑑”⟩} ∈ Fin)
13	12	ralrimiva 2945	. . . . . . . 8 ⊢ (((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ 𝑐 ∈ (𝐺 NeighbVtx 𝑣)) → ∀𝑑 ∈ ((𝐺 NeighbVtx 𝑣) ∖ {𝑐}){⟨“𝑐𝑣𝑑”⟩} ∈ Fin)
14		iunfi 8111	. . . . . . . 8 ⊢ ((((𝐺 NeighbVtx 𝑣) ∖ {𝑐}) ∈ Fin ∧ ∀𝑑 ∈ ((𝐺 NeighbVtx 𝑣) ∖ {𝑐}){⟨“𝑐𝑣𝑑”⟩} ∈ Fin) → ∪ 𝑑 ∈ ((𝐺 NeighbVtx 𝑣) ∖ {𝑐}){⟨“𝑐𝑣𝑑”⟩} ∈ Fin)
15	10, 13, 14	syl2anc 690	. . . . . . 7 ⊢ (((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ 𝑐 ∈ (𝐺 NeighbVtx 𝑣)) → ∪ 𝑑 ∈ ((𝐺 NeighbVtx 𝑣) ∖ {𝑐}){⟨“𝑐𝑣𝑑”⟩} ∈ Fin)
16	1	nbgrssvtx 40581	. . . . . . . . . . . 12 ⊢ (𝐺 ∈ FinUSGraph → (𝐺 NeighbVtx 𝑣) ⊆ 𝑉)
17	16	ad2antrr 757	. . . . . . . . . . 11 ⊢ (((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ 𝑐 ∈ (𝐺 NeighbVtx 𝑣)) → (𝐺 NeighbVtx 𝑣) ⊆ 𝑉)
18	17	ssdifd 3704	. . . . . . . . . 10 ⊢ (((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ 𝑐 ∈ (𝐺 NeighbVtx 𝑣)) → ((𝐺 NeighbVtx 𝑣) ∖ {𝑐}) ⊆ (𝑉 ∖ {𝑐}))
19		iunss1 4459	. . . . . . . . . 10 ⊢ (((𝐺 NeighbVtx 𝑣) ∖ {𝑐}) ⊆ (𝑉 ∖ {𝑐}) → ∪ 𝑑 ∈ ((𝐺 NeighbVtx 𝑣) ∖ {𝑐}){⟨“𝑐𝑣𝑑”⟩} ⊆ ∪ 𝑑 ∈ (𝑉 ∖ {𝑐}){⟨“𝑐𝑣𝑑”⟩})
20	18, 19	syl 17	. . . . . . . . 9 ⊢ (((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ 𝑐 ∈ (𝐺 NeighbVtx 𝑣)) → ∪ 𝑑 ∈ ((𝐺 NeighbVtx 𝑣) ∖ {𝑐}){⟨“𝑐𝑣𝑑”⟩} ⊆ ∪ 𝑑 ∈ (𝑉 ∖ {𝑐}){⟨“𝑐𝑣𝑑”⟩})
21	20	ralrimiva 2945	. . . . . . . 8 ⊢ ((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) → ∀𝑐 ∈ (𝐺 NeighbVtx 𝑣)∪ 𝑑 ∈ ((𝐺 NeighbVtx 𝑣) ∖ {𝑐}){⟨“𝑐𝑣𝑑”⟩} ⊆ ∪ 𝑑 ∈ (𝑉 ∖ {𝑐}){⟨“𝑐𝑣𝑑”⟩})
22		simpr 475	. . . . . . . . 9 ⊢ ((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) → 𝑣 ∈ 𝑉)
23		s3iunsndisj 13498	. . . . . . . . 9 ⊢ (𝑣 ∈ 𝑉 → Disj 𝑐 ∈ (𝐺 NeighbVtx 𝑣)∪ 𝑑 ∈ (𝑉 ∖ {𝑐}){⟨“𝑐𝑣𝑑”⟩})
24	22, 23	syl 17	. . . . . . . 8 ⊢ ((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) → Disj 𝑐 ∈ (𝐺 NeighbVtx 𝑣)∪ 𝑑 ∈ (𝑉 ∖ {𝑐}){⟨“𝑐𝑣𝑑”⟩})
25		disjss2 4547	. . . . . . . 8 ⊢ (∀𝑐 ∈ (𝐺 NeighbVtx 𝑣)∪ 𝑑 ∈ ((𝐺 NeighbVtx 𝑣) ∖ {𝑐}){⟨“𝑐𝑣𝑑”⟩} ⊆ ∪ 𝑑 ∈ (𝑉 ∖ {𝑐}){⟨“𝑐𝑣𝑑”⟩} → (Disj 𝑐 ∈ (𝐺 NeighbVtx 𝑣)∪ 𝑑 ∈ (𝑉 ∖ {𝑐}){⟨“𝑐𝑣𝑑”⟩} → Disj 𝑐 ∈ (𝐺 NeighbVtx 𝑣)∪ 𝑑 ∈ ((𝐺 NeighbVtx 𝑣) ∖ {𝑐}){⟨“𝑐𝑣𝑑”⟩}))
26	21, 24, 25	sylc 62	. . . . . . 7 ⊢ ((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) → Disj 𝑐 ∈ (𝐺 NeighbVtx 𝑣)∪ 𝑑 ∈ ((𝐺 NeighbVtx 𝑣) ∖ {𝑐}){⟨“𝑐𝑣𝑑”⟩})
27	7, 15, 26	hashiun 14338	. . . . . 6 ⊢ ((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) → (#‘∪ 𝑐 ∈ (𝐺 NeighbVtx 𝑣)∪ 𝑑 ∈ ((𝐺 NeighbVtx 𝑣) ∖ {𝑐}){⟨“𝑐𝑣𝑑”⟩}) = Σ𝑐 ∈ (𝐺 NeighbVtx 𝑣)(#‘∪ 𝑑 ∈ ((𝐺 NeighbVtx 𝑣) ∖ {𝑐}){⟨“𝑐𝑣𝑑”⟩}))
28	4, 27	eqtrd 2640	. . . . 5 ⊢ ((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) → (#‘(𝑀‘𝑣)) = Σ𝑐 ∈ (𝐺 NeighbVtx 𝑣)(#‘∪ 𝑑 ∈ ((𝐺 NeighbVtx 𝑣) ∖ {𝑐}){⟨“𝑐𝑣𝑑”⟩}))
29	28	adantr 479	. . . 4 ⊢ (((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ ((VtxDeg‘𝐺)‘𝑣) = 𝐾) → (#‘(𝑀‘𝑣)) = Σ𝑐 ∈ (𝐺 NeighbVtx 𝑣)(#‘∪ 𝑑 ∈ ((𝐺 NeighbVtx 𝑣) ∖ {𝑐}){⟨“𝑐𝑣𝑑”⟩}))
30	7, 9	syl 17	. . . . . . . 8 ⊢ ((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) → ((𝐺 NeighbVtx 𝑣) ∖ {𝑐}) ∈ Fin)
31	30	ad2antrr 757	. . . . . . 7 ⊢ ((((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ ((VtxDeg‘𝐺)‘𝑣) = 𝐾) ∧ 𝑐 ∈ (𝐺 NeighbVtx 𝑣)) → ((𝐺 NeighbVtx 𝑣) ∖ {𝑐}) ∈ Fin)
32	11	a1i 11	. . . . . . 7 ⊢ (((((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ ((VtxDeg‘𝐺)‘𝑣) = 𝐾) ∧ 𝑐 ∈ (𝐺 NeighbVtx 𝑣)) ∧ 𝑑 ∈ ((𝐺 NeighbVtx 𝑣) ∖ {𝑐})) → {⟨“𝑐𝑣𝑑”⟩} ∈ Fin)
33	22	adantr 479	. . . . . . . . . 10 ⊢ (((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ ((VtxDeg‘𝐺)‘𝑣) = 𝐾) → 𝑣 ∈ 𝑉)
34	33	anim1i 589	. . . . . . . . 9 ⊢ ((((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ ((VtxDeg‘𝐺)‘𝑣) = 𝐾) ∧ 𝑐 ∈ (𝐺 NeighbVtx 𝑣)) → (𝑣 ∈ 𝑉 ∧ 𝑐 ∈ (𝐺 NeighbVtx 𝑣)))
35	34	ancomd 465	. . . . . . . 8 ⊢ ((((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ ((VtxDeg‘𝐺)‘𝑣) = 𝐾) ∧ 𝑐 ∈ (𝐺 NeighbVtx 𝑣)) → (𝑐 ∈ (𝐺 NeighbVtx 𝑣) ∧ 𝑣 ∈ 𝑉))
36		s3sndisj 13497	. . . . . . . 8 ⊢ ((𝑐 ∈ (𝐺 NeighbVtx 𝑣) ∧ 𝑣 ∈ 𝑉) → Disj 𝑑 ∈ ((𝐺 NeighbVtx 𝑣) ∖ {𝑐}){⟨“𝑐𝑣𝑑”⟩})
37	35, 36	syl 17	. . . . . . 7 ⊢ ((((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ ((VtxDeg‘𝐺)‘𝑣) = 𝐾) ∧ 𝑐 ∈ (𝐺 NeighbVtx 𝑣)) → Disj 𝑑 ∈ ((𝐺 NeighbVtx 𝑣) ∖ {𝑐}){⟨“𝑐𝑣𝑑”⟩})
38	31, 32, 37	hashiun 14338	. . . . . 6 ⊢ ((((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ ((VtxDeg‘𝐺)‘𝑣) = 𝐾) ∧ 𝑐 ∈ (𝐺 NeighbVtx 𝑣)) → (#‘∪ 𝑑 ∈ ((𝐺 NeighbVtx 𝑣) ∖ {𝑐}){⟨“𝑐𝑣𝑑”⟩}) = Σ𝑑 ∈ ((𝐺 NeighbVtx 𝑣) ∖ {𝑐})(#‘{⟨“𝑐𝑣𝑑”⟩}))
39		s3cli 13419	. . . . . . . 8 ⊢ ⟨“𝑐𝑣𝑑”⟩ ∈ Word V
40		hashsng 12969	. . . . . . . 8 ⊢ (⟨“𝑐𝑣𝑑”⟩ ∈ Word V → (#‘{⟨“𝑐𝑣𝑑”⟩}) = 1)
41	39, 40	mp1i 13	. . . . . . 7 ⊢ (((((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ ((VtxDeg‘𝐺)‘𝑣) = 𝐾) ∧ 𝑐 ∈ (𝐺 NeighbVtx 𝑣)) ∧ 𝑑 ∈ ((𝐺 NeighbVtx 𝑣) ∖ {𝑐})) → (#‘{⟨“𝑐𝑣𝑑”⟩}) = 1)
42	41	sumeq2dv 14224	. . . . . 6 ⊢ ((((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ ((VtxDeg‘𝐺)‘𝑣) = 𝐾) ∧ 𝑐 ∈ (𝐺 NeighbVtx 𝑣)) → Σ𝑑 ∈ ((𝐺 NeighbVtx 𝑣) ∖ {𝑐})(#‘{⟨“𝑐𝑣𝑑”⟩}) = Σ𝑑 ∈ ((𝐺 NeighbVtx 𝑣) ∖ {𝑐})1)
43		ax-1cn 9847	. . . . . . 7 ⊢ 1 ∈ ℂ
44		fsumconst 14307	. . . . . . 7 ⊢ ((((𝐺 NeighbVtx 𝑣) ∖ {𝑐}) ∈ Fin ∧ 1 ∈ ℂ) → Σ𝑑 ∈ ((𝐺 NeighbVtx 𝑣) ∖ {𝑐})1 = ((#‘((𝐺 NeighbVtx 𝑣) ∖ {𝑐})) · 1))
45	31, 43, 44	sylancl 692	. . . . . 6 ⊢ ((((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ ((VtxDeg‘𝐺)‘𝑣) = 𝐾) ∧ 𝑐 ∈ (𝐺 NeighbVtx 𝑣)) → Σ𝑑 ∈ ((𝐺 NeighbVtx 𝑣) ∖ {𝑐})1 = ((#‘((𝐺 NeighbVtx 𝑣) ∖ {𝑐})) · 1))
46	38, 42, 45	3eqtrd 2644	. . . . 5 ⊢ ((((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ ((VtxDeg‘𝐺)‘𝑣) = 𝐾) ∧ 𝑐 ∈ (𝐺 NeighbVtx 𝑣)) → (#‘∪ 𝑑 ∈ ((𝐺 NeighbVtx 𝑣) ∖ {𝑐}){⟨“𝑐𝑣𝑑”⟩}) = ((#‘((𝐺 NeighbVtx 𝑣) ∖ {𝑐})) · 1))
47	46	sumeq2dv 14224	. . . 4 ⊢ (((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ ((VtxDeg‘𝐺)‘𝑣) = 𝐾) → Σ𝑐 ∈ (𝐺 NeighbVtx 𝑣)(#‘∪ 𝑑 ∈ ((𝐺 NeighbVtx 𝑣) ∖ {𝑐}){⟨“𝑐𝑣𝑑”⟩}) = Σ𝑐 ∈ (𝐺 NeighbVtx 𝑣)((#‘((𝐺 NeighbVtx 𝑣) ∖ {𝑐})) · 1))
48	7	adantr 479	. . . . . . . . 9 ⊢ (((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ ((VtxDeg‘𝐺)‘𝑣) = 𝐾) → (𝐺 NeighbVtx 𝑣) ∈ Fin)
49		hashdifsn 13012	. . . . . . . . 9 ⊢ (((𝐺 NeighbVtx 𝑣) ∈ Fin ∧ 𝑐 ∈ (𝐺 NeighbVtx 𝑣)) → (#‘((𝐺 NeighbVtx 𝑣) ∖ {𝑐})) = ((#‘(𝐺 NeighbVtx 𝑣)) − 1))
50	48, 49	sylan 486	. . . . . . . 8 ⊢ ((((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ ((VtxDeg‘𝐺)‘𝑣) = 𝐾) ∧ 𝑐 ∈ (𝐺 NeighbVtx 𝑣)) → (#‘((𝐺 NeighbVtx 𝑣) ∖ {𝑐})) = ((#‘(𝐺 NeighbVtx 𝑣)) − 1))
51	50	oveq1d 6539	. . . . . . 7 ⊢ ((((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ ((VtxDeg‘𝐺)‘𝑣) = 𝐾) ∧ 𝑐 ∈ (𝐺 NeighbVtx 𝑣)) → ((#‘((𝐺 NeighbVtx 𝑣) ∖ {𝑐})) · 1) = (((#‘(𝐺 NeighbVtx 𝑣)) − 1) · 1))
52	1	hashnbusgrnn0 40603	. . . . . . . . . 10 ⊢ ((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) → (#‘(𝐺 NeighbVtx 𝑣)) ∈ ℕ0)
53	52	nn0red 11196	. . . . . . . . 9 ⊢ ((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) → (#‘(𝐺 NeighbVtx 𝑣)) ∈ ℝ)
54		peano2rem 10196	. . . . . . . . 9 ⊢ ((#‘(𝐺 NeighbVtx 𝑣)) ∈ ℝ → ((#‘(𝐺 NeighbVtx 𝑣)) − 1) ∈ ℝ)
55		ax-1rid 9859	. . . . . . . . 9 ⊢ (((#‘(𝐺 NeighbVtx 𝑣)) − 1) ∈ ℝ → (((#‘(𝐺 NeighbVtx 𝑣)) − 1) · 1) = ((#‘(𝐺 NeighbVtx 𝑣)) − 1))
56	53, 54, 55	3syl 18	. . . . . . . 8 ⊢ ((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) → (((#‘(𝐺 NeighbVtx 𝑣)) − 1) · 1) = ((#‘(𝐺 NeighbVtx 𝑣)) − 1))
57	56	ad2antrr 757	. . . . . . 7 ⊢ ((((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ ((VtxDeg‘𝐺)‘𝑣) = 𝐾) ∧ 𝑐 ∈ (𝐺 NeighbVtx 𝑣)) → (((#‘(𝐺 NeighbVtx 𝑣)) − 1) · 1) = ((#‘(𝐺 NeighbVtx 𝑣)) − 1))
58	51, 57	eqtrd 2640	. . . . . 6 ⊢ ((((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ ((VtxDeg‘𝐺)‘𝑣) = 𝐾) ∧ 𝑐 ∈ (𝐺 NeighbVtx 𝑣)) → ((#‘((𝐺 NeighbVtx 𝑣) ∖ {𝑐})) · 1) = ((#‘(𝐺 NeighbVtx 𝑣)) − 1))
59	58	sumeq2dv 14224	. . . . 5 ⊢ (((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ ((VtxDeg‘𝐺)‘𝑣) = 𝐾) → Σ𝑐 ∈ (𝐺 NeighbVtx 𝑣)((#‘((𝐺 NeighbVtx 𝑣) ∖ {𝑐})) · 1) = Σ𝑐 ∈ (𝐺 NeighbVtx 𝑣)((#‘(𝐺 NeighbVtx 𝑣)) − 1))
60	52	nn0cnd 11197	. . . . . . . 8 ⊢ ((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) → (#‘(𝐺 NeighbVtx 𝑣)) ∈ ℂ)
61		1cnd 9909	. . . . . . . 8 ⊢ ((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) → 1 ∈ ℂ)
62	60, 61	subcld 10240	. . . . . . 7 ⊢ ((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) → ((#‘(𝐺 NeighbVtx 𝑣)) − 1) ∈ ℂ)
63	62	adantr 479	. . . . . 6 ⊢ (((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ ((VtxDeg‘𝐺)‘𝑣) = 𝐾) → ((#‘(𝐺 NeighbVtx 𝑣)) − 1) ∈ ℂ)
64		fsumconst 14307	. . . . . 6 ⊢ (((𝐺 NeighbVtx 𝑣) ∈ Fin ∧ ((#‘(𝐺 NeighbVtx 𝑣)) − 1) ∈ ℂ) → Σ𝑐 ∈ (𝐺 NeighbVtx 𝑣)((#‘(𝐺 NeighbVtx 𝑣)) − 1) = ((#‘(𝐺 NeighbVtx 𝑣)) · ((#‘(𝐺 NeighbVtx 𝑣)) − 1)))
65	48, 63, 64	syl2anc 690	. . . . 5 ⊢ (((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ ((VtxDeg‘𝐺)‘𝑣) = 𝐾) → Σ𝑐 ∈ (𝐺 NeighbVtx 𝑣)((#‘(𝐺 NeighbVtx 𝑣)) − 1) = ((#‘(𝐺 NeighbVtx 𝑣)) · ((#‘(𝐺 NeighbVtx 𝑣)) − 1)))
66		fusgrusgr 40540	. . . . . . . 8 ⊢ (𝐺 ∈ FinUSGraph → 𝐺 ∈ USGraph )
67	1	hashnbusgrvd 40743	. . . . . . . 8 ⊢ ((𝐺 ∈ USGraph ∧ 𝑣 ∈ 𝑉) → (#‘(𝐺 NeighbVtx 𝑣)) = ((VtxDeg‘𝐺)‘𝑣))
68	66, 67	sylan 486	. . . . . . 7 ⊢ ((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) → (#‘(𝐺 NeighbVtx 𝑣)) = ((VtxDeg‘𝐺)‘𝑣))
69		eqeq1 2610	. . . . . . . . 9 ⊢ (((VtxDeg‘𝐺)‘𝑣) = (#‘(𝐺 NeighbVtx 𝑣)) → (((VtxDeg‘𝐺)‘𝑣) = 𝐾 ↔ (#‘(𝐺 NeighbVtx 𝑣)) = 𝐾))
70	69	eqcoms 2614	. . . . . . . 8 ⊢ ((#‘(𝐺 NeighbVtx 𝑣)) = ((VtxDeg‘𝐺)‘𝑣) → (((VtxDeg‘𝐺)‘𝑣) = 𝐾 ↔ (#‘(𝐺 NeighbVtx 𝑣)) = 𝐾))
71		id 22	. . . . . . . . 9 ⊢ ((#‘(𝐺 NeighbVtx 𝑣)) = 𝐾 → (#‘(𝐺 NeighbVtx 𝑣)) = 𝐾)
72		oveq1 6531	. . . . . . . . 9 ⊢ ((#‘(𝐺 NeighbVtx 𝑣)) = 𝐾 → ((#‘(𝐺 NeighbVtx 𝑣)) − 1) = (𝐾 − 1))
73	71, 72	oveq12d 6542	. . . . . . . 8 ⊢ ((#‘(𝐺 NeighbVtx 𝑣)) = 𝐾 → ((#‘(𝐺 NeighbVtx 𝑣)) · ((#‘(𝐺 NeighbVtx 𝑣)) − 1)) = (𝐾 · (𝐾 − 1)))
74	70, 73	syl6bi 241	. . . . . . 7 ⊢ ((#‘(𝐺 NeighbVtx 𝑣)) = ((VtxDeg‘𝐺)‘𝑣) → (((VtxDeg‘𝐺)‘𝑣) = 𝐾 → ((#‘(𝐺 NeighbVtx 𝑣)) · ((#‘(𝐺 NeighbVtx 𝑣)) − 1)) = (𝐾 · (𝐾 − 1))))
75	68, 74	syl 17	. . . . . 6 ⊢ ((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) → (((VtxDeg‘𝐺)‘𝑣) = 𝐾 → ((#‘(𝐺 NeighbVtx 𝑣)) · ((#‘(𝐺 NeighbVtx 𝑣)) − 1)) = (𝐾 · (𝐾 − 1))))
76	75	imp 443	. . . . 5 ⊢ (((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ ((VtxDeg‘𝐺)‘𝑣) = 𝐾) → ((#‘(𝐺 NeighbVtx 𝑣)) · ((#‘(𝐺 NeighbVtx 𝑣)) − 1)) = (𝐾 · (𝐾 − 1)))
77	59, 65, 76	3eqtrd 2644	. . . 4 ⊢ (((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ ((VtxDeg‘𝐺)‘𝑣) = 𝐾) → Σ𝑐 ∈ (𝐺 NeighbVtx 𝑣)((#‘((𝐺 NeighbVtx 𝑣) ∖ {𝑐})) · 1) = (𝐾 · (𝐾 − 1)))
78	29, 47, 77	3eqtrd 2644	. . 3 ⊢ (((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) ∧ ((VtxDeg‘𝐺)‘𝑣) = 𝐾) → (#‘(𝑀‘𝑣)) = (𝐾 · (𝐾 − 1)))
79	78	ex 448	. 2 ⊢ ((𝐺 ∈ FinUSGraph ∧ 𝑣 ∈ 𝑉) → (((VtxDeg‘𝐺)‘𝑣) = 𝐾 → (#‘(𝑀‘𝑣)) = (𝐾 · (𝐾 − 1))))
80	79	ralrimiva 2945	1 ⊢ (𝐺 ∈ FinUSGraph → ∀𝑣 ∈ 𝑉 (((VtxDeg‘𝐺)‘𝑣) = 𝐾 → (#‘(𝑀‘𝑣)) = (𝐾 · (𝐾 − 1))))

Syntax hints:   → wi 4   ↔ wb 194   ∧ wa 382   = wceq 1474   ∈ wcel 1976  ∀wral 2892  {crab 2896  Vcvv 3169   ∖ cdif 3533   ⊆ wss 3536  {csn 4121  ∪ ciun 4446  Disj wdisj 4544   ↦ cmpt 4634  ‘cfv 5787  (class class class)co 6524  Fincfn 7815  ℂcc 9787  ℝcr 9788  1c1 9790   · cmul 9794   − cmin 10114  2c2 10914  #chash 12931  Word cword 13089  ⟨“cs3 13381  Σcsu 14207  Vtxcvtx 40228   USGraph cusgr 40378   FinUSGraph cfusgr 40534   NeighbVtx cnbgr 40549  VtxDegcvtxdg 40680   WSPathsN cwwspthsn 41030

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1712  ax-4 1727  ax-5 1826  ax-6 1874  ax-7 1921  ax-8 1978  ax-9 1985  ax-10 2005  ax-11 2020  ax-12 2032  ax-13 2229  ax-ext 2586  ax-rep 4690  ax-sep 4700  ax-nul 4709  ax-pow 4761  ax-pr 4825  ax-un 6821  ax-inf2 8395  ax-ac2 9142  ax-cnex 9845  ax-resscn 9846  ax-1cn 9847  ax-icn 9848  ax-addcl 9849  ax-addrcl 9850  ax-mulcl 9851  ax-mulrcl 9852  ax-mulcom 9853  ax-addass 9854  ax-mulass 9855  ax-distr 9856  ax-i2m1 9857  ax-1ne0 9858  ax-1rid 9859  ax-rnegex 9860  ax-rrecex 9861  ax-cnre 9862  ax-pre-lttri 9863  ax-pre-lttrn 9864  ax-pre-ltadd 9865  ax-pre-mulgt0 9866  ax-pre-sup 9867

This theorem depends on definitions:  df-bi 195  df-or 383  df-an 384  df-ifp 1006  df-3or 1031  df-3an 1032  df-tru 1477  df-fal 1480  df-ex 1695  df-nf 1700  df-sb 1867  df-eu 2458  df-mo 2459  df-clab 2593  df-cleq 2599  df-clel 2602  df-nfc 2736  df-ne 2778  df-nel 2779  df-ral 2897  df-rex 2898  df-reu 2899  df-rmo 2900  df-rab 2901  df-v 3171  df-sbc 3399  df-csb 3496  df-dif 3539  df-un 3541  df-in 3543  df-ss 3550  df-pss 3552  df-nul 3871  df-if 4033  df-pw 4106  df-sn 4122  df-pr 4124  df-tp 4126  df-op 4128  df-uni 4364  df-int 4402  df-iun 4448  df-disj 4545  df-br 4575  df-opab 4635  df-mpt 4636  df-tr 4672  df-eprel 4936  df-id 4940  df-po 4946  df-so 4947  df-fr 4984  df-se 4985  df-we 4986  df-xp 5031  df-rel 5032  df-cnv 5033  df-co 5034  df-dm 5035  df-rn 5036  df-res 5037  df-ima 5038  df-pred 5580  df-ord 5626  df-on 5627  df-lim 5628  df-suc 5629  df-iota 5751  df-fun 5789  df-fn 5790  df-f 5791  df-f1 5792  df-fo 5793  df-f1o 5794  df-fv 5795  df-isom 5796  df-riota 6486  df-ov 6527  df-oprab 6528  df-mpt2 6529  df-om 6932  df-1st 7033  df-2nd 7034  df-wrecs 7268  df-recs 7329  df-rdg 7367  df-1o 7421  df-2o 7422  df-oadd 7425  df-er 7603  df-map 7720  df-pm 7721  df-en 7816  df-dom 7817  df-sdom 7818  df-fin 7819  df-sup 8205  df-oi 8272  df-card 8622  df-ac 8796  df-cda 8847  df-pnf 9929  df-mnf 9930  df-xr 9931  df-ltxr 9932  df-le 9933  df-sub 10116  df-neg 10117  df-div 10531  df-nn 10865  df-2 10923  df-3 10924  df-n0 11137  df-z 11208  df-uz 11517  df-rp 11662  df-xadd 11776  df-fz 12150  df-fzo 12287  df-seq 12616  df-exp 12675  df-hash 12932  df-word 13097  df-concat 13099  df-s1 13100  df-s2 13387  df-s3 13388  df-cj 13630  df-re 13631  df-im 13632  df-sqrt 13766  df-abs 13767  df-clim 14010  df-sum 14208  df-xnn0 40197  df-vtx 40230  df-iedg 40231  df-uhgr 40279  df-ushgr 40280  df-upgr 40307  df-umgr 40308  df-edga 40351  df-uspgr 40379  df-usgr 40380  df-fusgr 40535  df-nbgr 40553  df-vtxdg 40681  df-1wlks 40799  df-wlks 40800  df-wlkson 40801  df-trls 40900  df-trlson 40901  df-pths 40922  df-spths 40923  df-pthson 40924  df-spthson 40925  df-wwlks 41032  df-wwlksn 41033  df-wwlksnon 41034  df-wspthsn 41035  df-wspthsnon 41036

This theorem is referenced by:  fusgreghash2wsp  41501