Step |
Hyp |
Ref |
Expression |
1 |
|
cusgrsizeindb0.v |
⊢ 𝑉 = ( Vtx ‘ 𝐺 ) |
2 |
|
cusgrsizeindb0.e |
⊢ 𝐸 = ( Edg ‘ 𝐺 ) |
3 |
|
cusgrcplgr |
⊢ ( 𝐺 ∈ ComplUSGraph → 𝐺 ∈ ComplGraph ) |
4 |
1
|
nbcplgr |
⊢ ( ( 𝐺 ∈ ComplGraph ∧ 𝑁 ∈ 𝑉 ) → ( 𝐺 NeighbVtx 𝑁 ) = ( 𝑉 ∖ { 𝑁 } ) ) |
5 |
3 4
|
sylan |
⊢ ( ( 𝐺 ∈ ComplUSGraph ∧ 𝑁 ∈ 𝑉 ) → ( 𝐺 NeighbVtx 𝑁 ) = ( 𝑉 ∖ { 𝑁 } ) ) |
6 |
5
|
3adant2 |
⊢ ( ( 𝐺 ∈ ComplUSGraph ∧ 𝑉 ∈ Fin ∧ 𝑁 ∈ 𝑉 ) → ( 𝐺 NeighbVtx 𝑁 ) = ( 𝑉 ∖ { 𝑁 } ) ) |
7 |
6
|
fveq2d |
⊢ ( ( 𝐺 ∈ ComplUSGraph ∧ 𝑉 ∈ Fin ∧ 𝑁 ∈ 𝑉 ) → ( ♯ ‘ ( 𝐺 NeighbVtx 𝑁 ) ) = ( ♯ ‘ ( 𝑉 ∖ { 𝑁 } ) ) ) |
8 |
|
cusgrusgr |
⊢ ( 𝐺 ∈ ComplUSGraph → 𝐺 ∈ USGraph ) |
9 |
8
|
anim1i |
⊢ ( ( 𝐺 ∈ ComplUSGraph ∧ 𝑁 ∈ 𝑉 ) → ( 𝐺 ∈ USGraph ∧ 𝑁 ∈ 𝑉 ) ) |
10 |
9
|
3adant2 |
⊢ ( ( 𝐺 ∈ ComplUSGraph ∧ 𝑉 ∈ Fin ∧ 𝑁 ∈ 𝑉 ) → ( 𝐺 ∈ USGraph ∧ 𝑁 ∈ 𝑉 ) ) |
11 |
1 2
|
nbusgrf1o |
⊢ ( ( 𝐺 ∈ USGraph ∧ 𝑁 ∈ 𝑉 ) → ∃ 𝑓 𝑓 : ( 𝐺 NeighbVtx 𝑁 ) –1-1-onto→ { 𝑒 ∈ 𝐸 ∣ 𝑁 ∈ 𝑒 } ) |
12 |
10 11
|
syl |
⊢ ( ( 𝐺 ∈ ComplUSGraph ∧ 𝑉 ∈ Fin ∧ 𝑁 ∈ 𝑉 ) → ∃ 𝑓 𝑓 : ( 𝐺 NeighbVtx 𝑁 ) –1-1-onto→ { 𝑒 ∈ 𝐸 ∣ 𝑁 ∈ 𝑒 } ) |
13 |
1 2
|
nbusgr |
⊢ ( 𝐺 ∈ USGraph → ( 𝐺 NeighbVtx 𝑁 ) = { 𝑛 ∈ 𝑉 ∣ { 𝑁 , 𝑛 } ∈ 𝐸 } ) |
14 |
8 13
|
syl |
⊢ ( 𝐺 ∈ ComplUSGraph → ( 𝐺 NeighbVtx 𝑁 ) = { 𝑛 ∈ 𝑉 ∣ { 𝑁 , 𝑛 } ∈ 𝐸 } ) |
15 |
14
|
adantr |
⊢ ( ( 𝐺 ∈ ComplUSGraph ∧ 𝑉 ∈ Fin ) → ( 𝐺 NeighbVtx 𝑁 ) = { 𝑛 ∈ 𝑉 ∣ { 𝑁 , 𝑛 } ∈ 𝐸 } ) |
16 |
|
rabfi |
⊢ ( 𝑉 ∈ Fin → { 𝑛 ∈ 𝑉 ∣ { 𝑁 , 𝑛 } ∈ 𝐸 } ∈ Fin ) |
17 |
16
|
adantl |
⊢ ( ( 𝐺 ∈ ComplUSGraph ∧ 𝑉 ∈ Fin ) → { 𝑛 ∈ 𝑉 ∣ { 𝑁 , 𝑛 } ∈ 𝐸 } ∈ Fin ) |
18 |
15 17
|
eqeltrd |
⊢ ( ( 𝐺 ∈ ComplUSGraph ∧ 𝑉 ∈ Fin ) → ( 𝐺 NeighbVtx 𝑁 ) ∈ Fin ) |
19 |
18
|
3adant3 |
⊢ ( ( 𝐺 ∈ ComplUSGraph ∧ 𝑉 ∈ Fin ∧ 𝑁 ∈ 𝑉 ) → ( 𝐺 NeighbVtx 𝑁 ) ∈ Fin ) |
20 |
8
|
anim1i |
⊢ ( ( 𝐺 ∈ ComplUSGraph ∧ 𝑉 ∈ Fin ) → ( 𝐺 ∈ USGraph ∧ 𝑉 ∈ Fin ) ) |
21 |
1
|
isfusgr |
⊢ ( 𝐺 ∈ FinUSGraph ↔ ( 𝐺 ∈ USGraph ∧ 𝑉 ∈ Fin ) ) |
22 |
20 21
|
sylibr |
⊢ ( ( 𝐺 ∈ ComplUSGraph ∧ 𝑉 ∈ Fin ) → 𝐺 ∈ FinUSGraph ) |
23 |
|
fusgrfis |
⊢ ( 𝐺 ∈ FinUSGraph → ( Edg ‘ 𝐺 ) ∈ Fin ) |
24 |
2 23
|
eqeltrid |
⊢ ( 𝐺 ∈ FinUSGraph → 𝐸 ∈ Fin ) |
25 |
|
rabfi |
⊢ ( 𝐸 ∈ Fin → { 𝑒 ∈ 𝐸 ∣ 𝑁 ∈ 𝑒 } ∈ Fin ) |
26 |
24 25
|
syl |
⊢ ( 𝐺 ∈ FinUSGraph → { 𝑒 ∈ 𝐸 ∣ 𝑁 ∈ 𝑒 } ∈ Fin ) |
27 |
22 26
|
syl |
⊢ ( ( 𝐺 ∈ ComplUSGraph ∧ 𝑉 ∈ Fin ) → { 𝑒 ∈ 𝐸 ∣ 𝑁 ∈ 𝑒 } ∈ Fin ) |
28 |
27
|
3adant3 |
⊢ ( ( 𝐺 ∈ ComplUSGraph ∧ 𝑉 ∈ Fin ∧ 𝑁 ∈ 𝑉 ) → { 𝑒 ∈ 𝐸 ∣ 𝑁 ∈ 𝑒 } ∈ Fin ) |
29 |
|
hasheqf1o |
⊢ ( ( ( 𝐺 NeighbVtx 𝑁 ) ∈ Fin ∧ { 𝑒 ∈ 𝐸 ∣ 𝑁 ∈ 𝑒 } ∈ Fin ) → ( ( ♯ ‘ ( 𝐺 NeighbVtx 𝑁 ) ) = ( ♯ ‘ { 𝑒 ∈ 𝐸 ∣ 𝑁 ∈ 𝑒 } ) ↔ ∃ 𝑓 𝑓 : ( 𝐺 NeighbVtx 𝑁 ) –1-1-onto→ { 𝑒 ∈ 𝐸 ∣ 𝑁 ∈ 𝑒 } ) ) |
30 |
19 28 29
|
syl2anc |
⊢ ( ( 𝐺 ∈ ComplUSGraph ∧ 𝑉 ∈ Fin ∧ 𝑁 ∈ 𝑉 ) → ( ( ♯ ‘ ( 𝐺 NeighbVtx 𝑁 ) ) = ( ♯ ‘ { 𝑒 ∈ 𝐸 ∣ 𝑁 ∈ 𝑒 } ) ↔ ∃ 𝑓 𝑓 : ( 𝐺 NeighbVtx 𝑁 ) –1-1-onto→ { 𝑒 ∈ 𝐸 ∣ 𝑁 ∈ 𝑒 } ) ) |
31 |
12 30
|
mpbird |
⊢ ( ( 𝐺 ∈ ComplUSGraph ∧ 𝑉 ∈ Fin ∧ 𝑁 ∈ 𝑉 ) → ( ♯ ‘ ( 𝐺 NeighbVtx 𝑁 ) ) = ( ♯ ‘ { 𝑒 ∈ 𝐸 ∣ 𝑁 ∈ 𝑒 } ) ) |
32 |
|
hashdifsn |
⊢ ( ( 𝑉 ∈ Fin ∧ 𝑁 ∈ 𝑉 ) → ( ♯ ‘ ( 𝑉 ∖ { 𝑁 } ) ) = ( ( ♯ ‘ 𝑉 ) − 1 ) ) |
33 |
32
|
3adant1 |
⊢ ( ( 𝐺 ∈ ComplUSGraph ∧ 𝑉 ∈ Fin ∧ 𝑁 ∈ 𝑉 ) → ( ♯ ‘ ( 𝑉 ∖ { 𝑁 } ) ) = ( ( ♯ ‘ 𝑉 ) − 1 ) ) |
34 |
7 31 33
|
3eqtr3d |
⊢ ( ( 𝐺 ∈ ComplUSGraph ∧ 𝑉 ∈ Fin ∧ 𝑁 ∈ 𝑉 ) → ( ♯ ‘ { 𝑒 ∈ 𝐸 ∣ 𝑁 ∈ 𝑒 } ) = ( ( ♯ ‘ 𝑉 ) − 1 ) ) |