Step | Hyp | Ref
| Expression |
1 | | cusgrsizeindb0.e |
. . . . 5
⊢ 𝐸 = (Edg‘𝐺) |
2 | | edgval 26997 |
. . . . 5
⊢
(Edg‘𝐺) = ran
(iEdg‘𝐺) |
3 | 1, 2 | eqtri 2762 |
. . . 4
⊢ 𝐸 = ran (iEdg‘𝐺) |
4 | 3 | a1i 11 |
. . 3
⊢ ((𝐺 ∈ ComplUSGraph ∧ 𝑉 ∈ Fin) → 𝐸 = ran (iEdg‘𝐺)) |
5 | 4 | fveq2d 6681 |
. 2
⊢ ((𝐺 ∈ ComplUSGraph ∧ 𝑉 ∈ Fin) →
(♯‘𝐸) =
(♯‘ran (iEdg‘𝐺))) |
6 | | cusgrsizeindb0.v |
. . . . 5
⊢ 𝑉 = (Vtx‘𝐺) |
7 | 6 | opeq1i 4765 |
. . . 4
⊢
〈𝑉,
(iEdg‘𝐺)〉 =
〈(Vtx‘𝐺),
(iEdg‘𝐺)〉 |
8 | | cusgrop 27383 |
. . . 4
⊢ (𝐺 ∈ ComplUSGraph →
〈(Vtx‘𝐺),
(iEdg‘𝐺)〉 ∈
ComplUSGraph) |
9 | 7, 8 | eqeltrid 2838 |
. . 3
⊢ (𝐺 ∈ ComplUSGraph →
〈𝑉, (iEdg‘𝐺)〉 ∈
ComplUSGraph) |
10 | | fvex 6690 |
. . . 4
⊢
(iEdg‘𝐺)
∈ V |
11 | | fvex 6690 |
. . . . 5
⊢
(Edg‘〈𝑣,
𝑒〉) ∈
V |
12 | | rabexg 5200 |
. . . . . 6
⊢
((Edg‘〈𝑣,
𝑒〉) ∈ V →
{𝑐 ∈
(Edg‘〈𝑣, 𝑒〉) ∣ 𝑛 ∉ 𝑐} ∈ V) |
13 | 12 | resiexd 6992 |
. . . . 5
⊢
((Edg‘〈𝑣,
𝑒〉) ∈ V → (
I ↾ {𝑐 ∈
(Edg‘〈𝑣, 𝑒〉) ∣ 𝑛 ∉ 𝑐}) ∈ V) |
14 | 11, 13 | ax-mp 5 |
. . . 4
⊢ ( I
↾ {𝑐 ∈
(Edg‘〈𝑣, 𝑒〉) ∣ 𝑛 ∉ 𝑐}) ∈ V |
15 | | rneq 5780 |
. . . . . 6
⊢ (𝑒 = (iEdg‘𝐺) → ran 𝑒 = ran (iEdg‘𝐺)) |
16 | 15 | fveq2d 6681 |
. . . . 5
⊢ (𝑒 = (iEdg‘𝐺) → (♯‘ran 𝑒) = (♯‘ran
(iEdg‘𝐺))) |
17 | | fveq2 6677 |
. . . . . 6
⊢ (𝑣 = 𝑉 → (♯‘𝑣) = (♯‘𝑉)) |
18 | 17 | oveq1d 7188 |
. . . . 5
⊢ (𝑣 = 𝑉 → ((♯‘𝑣)C2) = ((♯‘𝑉)C2)) |
19 | 16, 18 | eqeqan12rd 2758 |
. . . 4
⊢ ((𝑣 = 𝑉 ∧ 𝑒 = (iEdg‘𝐺)) → ((♯‘ran 𝑒) = ((♯‘𝑣)C2) ↔ (♯‘ran
(iEdg‘𝐺)) =
((♯‘𝑉)C2))) |
20 | | rneq 5780 |
. . . . . 6
⊢ (𝑒 = 𝑓 → ran 𝑒 = ran 𝑓) |
21 | 20 | fveq2d 6681 |
. . . . 5
⊢ (𝑒 = 𝑓 → (♯‘ran 𝑒) = (♯‘ran 𝑓)) |
22 | | fveq2 6677 |
. . . . . 6
⊢ (𝑣 = 𝑤 → (♯‘𝑣) = (♯‘𝑤)) |
23 | 22 | oveq1d 7188 |
. . . . 5
⊢ (𝑣 = 𝑤 → ((♯‘𝑣)C2) = ((♯‘𝑤)C2)) |
24 | 21, 23 | eqeqan12rd 2758 |
. . . 4
⊢ ((𝑣 = 𝑤 ∧ 𝑒 = 𝑓) → ((♯‘ran 𝑒) = ((♯‘𝑣)C2) ↔ (♯‘ran
𝑓) = ((♯‘𝑤)C2))) |
25 | | vex 3403 |
. . . . . . 7
⊢ 𝑣 ∈ V |
26 | | vex 3403 |
. . . . . . 7
⊢ 𝑒 ∈ V |
27 | 25, 26 | opvtxfvi 26957 |
. . . . . 6
⊢
(Vtx‘〈𝑣,
𝑒〉) = 𝑣 |
28 | 27 | eqcomi 2748 |
. . . . 5
⊢ 𝑣 = (Vtx‘〈𝑣, 𝑒〉) |
29 | | eqid 2739 |
. . . . 5
⊢
(Edg‘〈𝑣,
𝑒〉) =
(Edg‘〈𝑣, 𝑒〉) |
30 | | eqid 2739 |
. . . . 5
⊢ {𝑐 ∈ (Edg‘〈𝑣, 𝑒〉) ∣ 𝑛 ∉ 𝑐} = {𝑐 ∈ (Edg‘〈𝑣, 𝑒〉) ∣ 𝑛 ∉ 𝑐} |
31 | | eqid 2739 |
. . . . 5
⊢
〈(𝑣 ∖
{𝑛}), ( I ↾ {𝑐 ∈ (Edg‘〈𝑣, 𝑒〉) ∣ 𝑛 ∉ 𝑐})〉 = 〈(𝑣 ∖ {𝑛}), ( I ↾ {𝑐 ∈ (Edg‘〈𝑣, 𝑒〉) ∣ 𝑛 ∉ 𝑐})〉 |
32 | 28, 29, 30, 31 | cusgrres 27393 |
. . . 4
⊢
((〈𝑣, 𝑒〉 ∈ ComplUSGraph ∧
𝑛 ∈ 𝑣) → 〈(𝑣 ∖ {𝑛}), ( I ↾ {𝑐 ∈ (Edg‘〈𝑣, 𝑒〉) ∣ 𝑛 ∉ 𝑐})〉 ∈
ComplUSGraph) |
33 | | rneq 5780 |
. . . . . . 7
⊢ (𝑓 = ( I ↾ {𝑐 ∈ (Edg‘〈𝑣, 𝑒〉) ∣ 𝑛 ∉ 𝑐}) → ran 𝑓 = ran ( I ↾ {𝑐 ∈ (Edg‘〈𝑣, 𝑒〉) ∣ 𝑛 ∉ 𝑐})) |
34 | 33 | fveq2d 6681 |
. . . . . 6
⊢ (𝑓 = ( I ↾ {𝑐 ∈ (Edg‘〈𝑣, 𝑒〉) ∣ 𝑛 ∉ 𝑐}) → (♯‘ran 𝑓) = (♯‘ran ( I
↾ {𝑐 ∈
(Edg‘〈𝑣, 𝑒〉) ∣ 𝑛 ∉ 𝑐}))) |
35 | 34 | adantl 485 |
. . . . 5
⊢ ((𝑤 = (𝑣 ∖ {𝑛}) ∧ 𝑓 = ( I ↾ {𝑐 ∈ (Edg‘〈𝑣, 𝑒〉) ∣ 𝑛 ∉ 𝑐})) → (♯‘ran 𝑓) = (♯‘ran ( I
↾ {𝑐 ∈
(Edg‘〈𝑣, 𝑒〉) ∣ 𝑛 ∉ 𝑐}))) |
36 | | fveq2 6677 |
. . . . . . 7
⊢ (𝑤 = (𝑣 ∖ {𝑛}) → (♯‘𝑤) = (♯‘(𝑣 ∖ {𝑛}))) |
37 | 36 | adantr 484 |
. . . . . 6
⊢ ((𝑤 = (𝑣 ∖ {𝑛}) ∧ 𝑓 = ( I ↾ {𝑐 ∈ (Edg‘〈𝑣, 𝑒〉) ∣ 𝑛 ∉ 𝑐})) → (♯‘𝑤) = (♯‘(𝑣 ∖ {𝑛}))) |
38 | 37 | oveq1d 7188 |
. . . . 5
⊢ ((𝑤 = (𝑣 ∖ {𝑛}) ∧ 𝑓 = ( I ↾ {𝑐 ∈ (Edg‘〈𝑣, 𝑒〉) ∣ 𝑛 ∉ 𝑐})) → ((♯‘𝑤)C2) = ((♯‘(𝑣 ∖ {𝑛}))C2)) |
39 | 35, 38 | eqeq12d 2755 |
. . . 4
⊢ ((𝑤 = (𝑣 ∖ {𝑛}) ∧ 𝑓 = ( I ↾ {𝑐 ∈ (Edg‘〈𝑣, 𝑒〉) ∣ 𝑛 ∉ 𝑐})) → ((♯‘ran 𝑓) = ((♯‘𝑤)C2) ↔ (♯‘ran (
I ↾ {𝑐 ∈
(Edg‘〈𝑣, 𝑒〉) ∣ 𝑛 ∉ 𝑐})) = ((♯‘(𝑣 ∖ {𝑛}))C2))) |
40 | | edgopval 26999 |
. . . . . . . . 9
⊢ ((𝑣 ∈ V ∧ 𝑒 ∈ V) →
(Edg‘〈𝑣, 𝑒〉) = ran 𝑒) |
41 | 40 | el2v 3407 |
. . . . . . . 8
⊢
(Edg‘〈𝑣,
𝑒〉) = ran 𝑒 |
42 | 41 | a1i 11 |
. . . . . . 7
⊢
((〈𝑣, 𝑒〉 ∈ ComplUSGraph ∧
(♯‘𝑣) = 0)
→ (Edg‘〈𝑣,
𝑒〉) = ran 𝑒) |
43 | 42 | eqcomd 2745 |
. . . . . 6
⊢
((〈𝑣, 𝑒〉 ∈ ComplUSGraph ∧
(♯‘𝑣) = 0)
→ ran 𝑒 =
(Edg‘〈𝑣, 𝑒〉)) |
44 | 43 | fveq2d 6681 |
. . . . 5
⊢
((〈𝑣, 𝑒〉 ∈ ComplUSGraph ∧
(♯‘𝑣) = 0)
→ (♯‘ran 𝑒) = (♯‘(Edg‘〈𝑣, 𝑒〉))) |
45 | | cusgrusgr 27364 |
. . . . . . 7
⊢
(〈𝑣, 𝑒〉 ∈ ComplUSGraph
→ 〈𝑣, 𝑒〉 ∈
USGraph) |
46 | | usgruhgr 27131 |
. . . . . . 7
⊢
(〈𝑣, 𝑒〉 ∈ USGraph →
〈𝑣, 𝑒〉 ∈ UHGraph) |
47 | 45, 46 | syl 17 |
. . . . . 6
⊢
(〈𝑣, 𝑒〉 ∈ ComplUSGraph
→ 〈𝑣, 𝑒〉 ∈
UHGraph) |
48 | 28, 29 | cusgrsizeindb0 27394 |
. . . . . 6
⊢
((〈𝑣, 𝑒〉 ∈ UHGraph ∧
(♯‘𝑣) = 0)
→ (♯‘(Edg‘〈𝑣, 𝑒〉)) = ((♯‘𝑣)C2)) |
49 | 47, 48 | sylan 583 |
. . . . 5
⊢
((〈𝑣, 𝑒〉 ∈ ComplUSGraph ∧
(♯‘𝑣) = 0)
→ (♯‘(Edg‘〈𝑣, 𝑒〉)) = ((♯‘𝑣)C2)) |
50 | 44, 49 | eqtrd 2774 |
. . . 4
⊢
((〈𝑣, 𝑒〉 ∈ ComplUSGraph ∧
(♯‘𝑣) = 0)
→ (♯‘ran 𝑒) = ((♯‘𝑣)C2)) |
51 | | rnresi 5918 |
. . . . . . . . . 10
⊢ ran ( I
↾ {𝑐 ∈
(Edg‘〈𝑣, 𝑒〉) ∣ 𝑛 ∉ 𝑐}) = {𝑐 ∈ (Edg‘〈𝑣, 𝑒〉) ∣ 𝑛 ∉ 𝑐} |
52 | 51 | fveq2i 6680 |
. . . . . . . . 9
⊢
(♯‘ran ( I ↾ {𝑐 ∈ (Edg‘〈𝑣, 𝑒〉) ∣ 𝑛 ∉ 𝑐})) = (♯‘{𝑐 ∈ (Edg‘〈𝑣, 𝑒〉) ∣ 𝑛 ∉ 𝑐}) |
53 | 41 | a1i 11 |
. . . . . . . . . . 11
⊢ (((𝑦 + 1) ∈ ℕ0
∧ (〈𝑣, 𝑒〉 ∈ ComplUSGraph ∧
(♯‘𝑣) = (𝑦 + 1) ∧ 𝑛 ∈ 𝑣)) → (Edg‘〈𝑣, 𝑒〉) = ran 𝑒) |
54 | 53 | rabeqdv 3387 |
. . . . . . . . . 10
⊢ (((𝑦 + 1) ∈ ℕ0
∧ (〈𝑣, 𝑒〉 ∈ ComplUSGraph ∧
(♯‘𝑣) = (𝑦 + 1) ∧ 𝑛 ∈ 𝑣)) → {𝑐 ∈ (Edg‘〈𝑣, 𝑒〉) ∣ 𝑛 ∉ 𝑐} = {𝑐 ∈ ran 𝑒 ∣ 𝑛 ∉ 𝑐}) |
55 | 54 | fveq2d 6681 |
. . . . . . . . 9
⊢ (((𝑦 + 1) ∈ ℕ0
∧ (〈𝑣, 𝑒〉 ∈ ComplUSGraph ∧
(♯‘𝑣) = (𝑦 + 1) ∧ 𝑛 ∈ 𝑣)) → (♯‘{𝑐 ∈ (Edg‘〈𝑣, 𝑒〉) ∣ 𝑛 ∉ 𝑐}) = (♯‘{𝑐 ∈ ran 𝑒 ∣ 𝑛 ∉ 𝑐})) |
56 | 52, 55 | syl5eq 2786 |
. . . . . . . 8
⊢ (((𝑦 + 1) ∈ ℕ0
∧ (〈𝑣, 𝑒〉 ∈ ComplUSGraph ∧
(♯‘𝑣) = (𝑦 + 1) ∧ 𝑛 ∈ 𝑣)) → (♯‘ran ( I ↾
{𝑐 ∈
(Edg‘〈𝑣, 𝑒〉) ∣ 𝑛 ∉ 𝑐})) = (♯‘{𝑐 ∈ ran 𝑒 ∣ 𝑛 ∉ 𝑐})) |
57 | 56 | eqeq1d 2741 |
. . . . . . 7
⊢ (((𝑦 + 1) ∈ ℕ0
∧ (〈𝑣, 𝑒〉 ∈ ComplUSGraph ∧
(♯‘𝑣) = (𝑦 + 1) ∧ 𝑛 ∈ 𝑣)) → ((♯‘ran ( I ↾
{𝑐 ∈
(Edg‘〈𝑣, 𝑒〉) ∣ 𝑛 ∉ 𝑐})) = ((♯‘(𝑣 ∖ {𝑛}))C2) ↔ (♯‘{𝑐 ∈ ran 𝑒 ∣ 𝑛 ∉ 𝑐}) = ((♯‘(𝑣 ∖ {𝑛}))C2))) |
58 | 57 | biimpd 232 |
. . . . . 6
⊢ (((𝑦 + 1) ∈ ℕ0
∧ (〈𝑣, 𝑒〉 ∈ ComplUSGraph ∧
(♯‘𝑣) = (𝑦 + 1) ∧ 𝑛 ∈ 𝑣)) → ((♯‘ran ( I ↾
{𝑐 ∈
(Edg‘〈𝑣, 𝑒〉) ∣ 𝑛 ∉ 𝑐})) = ((♯‘(𝑣 ∖ {𝑛}))C2) → (♯‘{𝑐 ∈ ran 𝑒 ∣ 𝑛 ∉ 𝑐}) = ((♯‘(𝑣 ∖ {𝑛}))C2))) |
59 | 58 | imdistani 572 |
. . . . 5
⊢ ((((𝑦 + 1) ∈ ℕ0
∧ (〈𝑣, 𝑒〉 ∈ ComplUSGraph ∧
(♯‘𝑣) = (𝑦 + 1) ∧ 𝑛 ∈ 𝑣)) ∧ (♯‘ran ( I ↾
{𝑐 ∈
(Edg‘〈𝑣, 𝑒〉) ∣ 𝑛 ∉ 𝑐})) = ((♯‘(𝑣 ∖ {𝑛}))C2)) → (((𝑦 + 1) ∈ ℕ0 ∧
(〈𝑣, 𝑒〉 ∈ ComplUSGraph ∧
(♯‘𝑣) = (𝑦 + 1) ∧ 𝑛 ∈ 𝑣)) ∧ (♯‘{𝑐 ∈ ran 𝑒 ∣ 𝑛 ∉ 𝑐}) = ((♯‘(𝑣 ∖ {𝑛}))C2))) |
60 | 41 | eqcomi 2748 |
. . . . . . 7
⊢ ran 𝑒 = (Edg‘〈𝑣, 𝑒〉) |
61 | | eqid 2739 |
. . . . . . 7
⊢ {𝑐 ∈ ran 𝑒 ∣ 𝑛 ∉ 𝑐} = {𝑐 ∈ ran 𝑒 ∣ 𝑛 ∉ 𝑐} |
62 | 28, 60, 61 | cusgrsize2inds 27398 |
. . . . . 6
⊢ ((𝑦 + 1) ∈ ℕ0
→ ((〈𝑣, 𝑒〉 ∈ ComplUSGraph ∧
(♯‘𝑣) = (𝑦 + 1) ∧ 𝑛 ∈ 𝑣) → ((♯‘{𝑐 ∈ ran 𝑒 ∣ 𝑛 ∉ 𝑐}) = ((♯‘(𝑣 ∖ {𝑛}))C2) → (♯‘ran 𝑒) = ((♯‘𝑣)C2)))) |
63 | 62 | imp31 421 |
. . . . 5
⊢ ((((𝑦 + 1) ∈ ℕ0
∧ (〈𝑣, 𝑒〉 ∈ ComplUSGraph ∧
(♯‘𝑣) = (𝑦 + 1) ∧ 𝑛 ∈ 𝑣)) ∧ (♯‘{𝑐 ∈ ran 𝑒 ∣ 𝑛 ∉ 𝑐}) = ((♯‘(𝑣 ∖ {𝑛}))C2)) → (♯‘ran 𝑒) = ((♯‘𝑣)C2)) |
64 | 59, 63 | syl 17 |
. . . 4
⊢ ((((𝑦 + 1) ∈ ℕ0
∧ (〈𝑣, 𝑒〉 ∈ ComplUSGraph ∧
(♯‘𝑣) = (𝑦 + 1) ∧ 𝑛 ∈ 𝑣)) ∧ (♯‘ran ( I ↾
{𝑐 ∈
(Edg‘〈𝑣, 𝑒〉) ∣ 𝑛 ∉ 𝑐})) = ((♯‘(𝑣 ∖ {𝑛}))C2)) → (♯‘ran 𝑒) = ((♯‘𝑣)C2)) |
65 | 10, 14, 19, 24, 32, 39, 50, 64 | opfi1ind 13957 |
. . 3
⊢
((〈𝑉,
(iEdg‘𝐺)〉 ∈
ComplUSGraph ∧ 𝑉 ∈
Fin) → (♯‘ran (iEdg‘𝐺)) = ((♯‘𝑉)C2)) |
66 | 9, 65 | sylan 583 |
. 2
⊢ ((𝐺 ∈ ComplUSGraph ∧ 𝑉 ∈ Fin) →
(♯‘ran (iEdg‘𝐺)) = ((♯‘𝑉)C2)) |
67 | 5, 66 | eqtrd 2774 |
1
⊢ ((𝐺 ∈ ComplUSGraph ∧ 𝑉 ∈ Fin) →
(♯‘𝐸) =
((♯‘𝑉)C2)) |