Metamath Proof Explorer


Theorem frgrncvvdeqlem9

Description: Lemma 9 for frgrncvvdeq . This corresponds to statement 3 in Huneke p. 1: "By symmetry the map is onto". (Contributed by Alexander van der Vekens, 24-Dec-2017) (Revised by AV, 10-May-2021) (Proof shortened by AV, 12-Feb-2022)

Ref Expression
Hypotheses frgrncvvdeq.v1 𝑉 = ( Vtx ‘ 𝐺 )
frgrncvvdeq.e 𝐸 = ( Edg ‘ 𝐺 )
frgrncvvdeq.nx 𝐷 = ( 𝐺 NeighbVtx 𝑋 )
frgrncvvdeq.ny 𝑁 = ( 𝐺 NeighbVtx 𝑌 )
frgrncvvdeq.x ( 𝜑𝑋𝑉 )
frgrncvvdeq.y ( 𝜑𝑌𝑉 )
frgrncvvdeq.ne ( 𝜑𝑋𝑌 )
frgrncvvdeq.xy ( 𝜑𝑌𝐷 )
frgrncvvdeq.f ( 𝜑𝐺 ∈ FriendGraph )
frgrncvvdeq.a 𝐴 = ( 𝑥𝐷 ↦ ( 𝑦𝑁 { 𝑥 , 𝑦 } ∈ 𝐸 ) )
Assertion frgrncvvdeqlem9 ( 𝜑𝐴 : 𝐷onto𝑁 )

Proof

Step Hyp Ref Expression
1 frgrncvvdeq.v1 𝑉 = ( Vtx ‘ 𝐺 )
2 frgrncvvdeq.e 𝐸 = ( Edg ‘ 𝐺 )
3 frgrncvvdeq.nx 𝐷 = ( 𝐺 NeighbVtx 𝑋 )
4 frgrncvvdeq.ny 𝑁 = ( 𝐺 NeighbVtx 𝑌 )
5 frgrncvvdeq.x ( 𝜑𝑋𝑉 )
6 frgrncvvdeq.y ( 𝜑𝑌𝑉 )
7 frgrncvvdeq.ne ( 𝜑𝑋𝑌 )
8 frgrncvvdeq.xy ( 𝜑𝑌𝐷 )
9 frgrncvvdeq.f ( 𝜑𝐺 ∈ FriendGraph )
10 frgrncvvdeq.a 𝐴 = ( 𝑥𝐷 ↦ ( 𝑦𝑁 { 𝑥 , 𝑦 } ∈ 𝐸 ) )
11 1 2 3 4 5 6 7 8 9 10 frgrncvvdeqlem4 ( 𝜑𝐴 : 𝐷𝑁 )
12 9 adantr ( ( 𝜑𝑛𝑁 ) → 𝐺 ∈ FriendGraph )
13 4 eleq2i ( 𝑛𝑁𝑛 ∈ ( 𝐺 NeighbVtx 𝑌 ) )
14 1 nbgrisvtx ( 𝑛 ∈ ( 𝐺 NeighbVtx 𝑌 ) → 𝑛𝑉 )
15 14 a1i ( 𝜑 → ( 𝑛 ∈ ( 𝐺 NeighbVtx 𝑌 ) → 𝑛𝑉 ) )
16 13 15 syl5bi ( 𝜑 → ( 𝑛𝑁𝑛𝑉 ) )
17 16 imp ( ( 𝜑𝑛𝑁 ) → 𝑛𝑉 )
18 5 adantr ( ( 𝜑𝑛𝑁 ) → 𝑋𝑉 )
19 1 2 3 4 5 6 7 8 9 10 frgrncvvdeqlem1 ( 𝜑𝑋𝑁 )
20 df-nel ( 𝑋𝑁 ↔ ¬ 𝑋𝑁 )
21 nelelne ( ¬ 𝑋𝑁 → ( 𝑛𝑁𝑛𝑋 ) )
22 20 21 sylbi ( 𝑋𝑁 → ( 𝑛𝑁𝑛𝑋 ) )
23 19 22 syl ( 𝜑 → ( 𝑛𝑁𝑛𝑋 ) )
24 23 imp ( ( 𝜑𝑛𝑁 ) → 𝑛𝑋 )
25 17 18 24 3jca ( ( 𝜑𝑛𝑁 ) → ( 𝑛𝑉𝑋𝑉𝑛𝑋 ) )
26 12 25 jca ( ( 𝜑𝑛𝑁 ) → ( 𝐺 ∈ FriendGraph ∧ ( 𝑛𝑉𝑋𝑉𝑛𝑋 ) ) )
27 1 2 frcond2 ( 𝐺 ∈ FriendGraph → ( ( 𝑛𝑉𝑋𝑉𝑛𝑋 ) → ∃! 𝑚𝑉 ( { 𝑛 , 𝑚 } ∈ 𝐸 ∧ { 𝑚 , 𝑋 } ∈ 𝐸 ) ) )
28 27 imp ( ( 𝐺 ∈ FriendGraph ∧ ( 𝑛𝑉𝑋𝑉𝑛𝑋 ) ) → ∃! 𝑚𝑉 ( { 𝑛 , 𝑚 } ∈ 𝐸 ∧ { 𝑚 , 𝑋 } ∈ 𝐸 ) )
29 reurex ( ∃! 𝑚𝑉 ( { 𝑛 , 𝑚 } ∈ 𝐸 ∧ { 𝑚 , 𝑋 } ∈ 𝐸 ) → ∃ 𝑚𝑉 ( { 𝑛 , 𝑚 } ∈ 𝐸 ∧ { 𝑚 , 𝑋 } ∈ 𝐸 ) )
30 df-rex ( ∃ 𝑚𝑉 ( { 𝑛 , 𝑚 } ∈ 𝐸 ∧ { 𝑚 , 𝑋 } ∈ 𝐸 ) ↔ ∃ 𝑚 ( 𝑚𝑉 ∧ ( { 𝑛 , 𝑚 } ∈ 𝐸 ∧ { 𝑚 , 𝑋 } ∈ 𝐸 ) ) )
31 29 30 sylib ( ∃! 𝑚𝑉 ( { 𝑛 , 𝑚 } ∈ 𝐸 ∧ { 𝑚 , 𝑋 } ∈ 𝐸 ) → ∃ 𝑚 ( 𝑚𝑉 ∧ ( { 𝑛 , 𝑚 } ∈ 𝐸 ∧ { 𝑚 , 𝑋 } ∈ 𝐸 ) ) )
32 26 28 31 3syl ( ( 𝜑𝑛𝑁 ) → ∃ 𝑚 ( 𝑚𝑉 ∧ ( { 𝑛 , 𝑚 } ∈ 𝐸 ∧ { 𝑚 , 𝑋 } ∈ 𝐸 ) ) )
33 frgrusgr ( 𝐺 ∈ FriendGraph → 𝐺 ∈ USGraph )
34 2 nbusgreledg ( 𝐺 ∈ USGraph → ( 𝑚 ∈ ( 𝐺 NeighbVtx 𝑋 ) ↔ { 𝑚 , 𝑋 } ∈ 𝐸 ) )
35 34 bicomd ( 𝐺 ∈ USGraph → ( { 𝑚 , 𝑋 } ∈ 𝐸𝑚 ∈ ( 𝐺 NeighbVtx 𝑋 ) ) )
36 9 33 35 3syl ( 𝜑 → ( { 𝑚 , 𝑋 } ∈ 𝐸𝑚 ∈ ( 𝐺 NeighbVtx 𝑋 ) ) )
37 36 biimpa ( ( 𝜑 ∧ { 𝑚 , 𝑋 } ∈ 𝐸 ) → 𝑚 ∈ ( 𝐺 NeighbVtx 𝑋 ) )
38 3 eleq2i ( 𝑚𝐷𝑚 ∈ ( 𝐺 NeighbVtx 𝑋 ) )
39 37 38 sylibr ( ( 𝜑 ∧ { 𝑚 , 𝑋 } ∈ 𝐸 ) → 𝑚𝐷 )
40 39 ad2ant2rl ( ( ( 𝜑𝑛𝑁 ) ∧ ( { 𝑛 , 𝑚 } ∈ 𝐸 ∧ { 𝑚 , 𝑋 } ∈ 𝐸 ) ) → 𝑚𝐷 )
41 2 nbusgreledg ( 𝐺 ∈ USGraph → ( 𝑛 ∈ ( 𝐺 NeighbVtx 𝑚 ) ↔ { 𝑛 , 𝑚 } ∈ 𝐸 ) )
42 41 biimpar ( ( 𝐺 ∈ USGraph ∧ { 𝑛 , 𝑚 } ∈ 𝐸 ) → 𝑛 ∈ ( 𝐺 NeighbVtx 𝑚 ) )
43 42 a1d ( ( 𝐺 ∈ USGraph ∧ { 𝑛 , 𝑚 } ∈ 𝐸 ) → ( { 𝑚 , 𝑋 } ∈ 𝐸𝑛 ∈ ( 𝐺 NeighbVtx 𝑚 ) ) )
44 43 expimpd ( 𝐺 ∈ USGraph → ( ( { 𝑛 , 𝑚 } ∈ 𝐸 ∧ { 𝑚 , 𝑋 } ∈ 𝐸 ) → 𝑛 ∈ ( 𝐺 NeighbVtx 𝑚 ) ) )
45 9 33 44 3syl ( 𝜑 → ( ( { 𝑛 , 𝑚 } ∈ 𝐸 ∧ { 𝑚 , 𝑋 } ∈ 𝐸 ) → 𝑛 ∈ ( 𝐺 NeighbVtx 𝑚 ) ) )
46 45 adantr ( ( 𝜑𝑛𝑁 ) → ( ( { 𝑛 , 𝑚 } ∈ 𝐸 ∧ { 𝑚 , 𝑋 } ∈ 𝐸 ) → 𝑛 ∈ ( 𝐺 NeighbVtx 𝑚 ) ) )
47 46 imp ( ( ( 𝜑𝑛𝑁 ) ∧ ( { 𝑛 , 𝑚 } ∈ 𝐸 ∧ { 𝑚 , 𝑋 } ∈ 𝐸 ) ) → 𝑛 ∈ ( 𝐺 NeighbVtx 𝑚 ) )
48 elin ( 𝑛 ∈ ( ( 𝐺 NeighbVtx 𝑚 ) ∩ 𝑁 ) ↔ ( 𝑛 ∈ ( 𝐺 NeighbVtx 𝑚 ) ∧ 𝑛𝑁 ) )
49 simpl ( ( 𝜑 ∧ { 𝑚 , 𝑋 } ∈ 𝐸 ) → 𝜑 )
50 49 39 jca ( ( 𝜑 ∧ { 𝑚 , 𝑋 } ∈ 𝐸 ) → ( 𝜑𝑚𝐷 ) )
51 preq1 ( 𝑥 = 𝑚 → { 𝑥 , 𝑦 } = { 𝑚 , 𝑦 } )
52 51 eleq1d ( 𝑥 = 𝑚 → ( { 𝑥 , 𝑦 } ∈ 𝐸 ↔ { 𝑚 , 𝑦 } ∈ 𝐸 ) )
53 52 riotabidv ( 𝑥 = 𝑚 → ( 𝑦𝑁 { 𝑥 , 𝑦 } ∈ 𝐸 ) = ( 𝑦𝑁 { 𝑚 , 𝑦 } ∈ 𝐸 ) )
54 53 cbvmptv ( 𝑥𝐷 ↦ ( 𝑦𝑁 { 𝑥 , 𝑦 } ∈ 𝐸 ) ) = ( 𝑚𝐷 ↦ ( 𝑦𝑁 { 𝑚 , 𝑦 } ∈ 𝐸 ) )
55 10 54 eqtri 𝐴 = ( 𝑚𝐷 ↦ ( 𝑦𝑁 { 𝑚 , 𝑦 } ∈ 𝐸 ) )
56 1 2 3 4 5 6 7 8 9 55 frgrncvvdeqlem5 ( ( 𝜑𝑚𝐷 ) → { ( 𝐴𝑚 ) } = ( ( 𝐺 NeighbVtx 𝑚 ) ∩ 𝑁 ) )
57 eleq2 ( ( ( 𝐺 NeighbVtx 𝑚 ) ∩ 𝑁 ) = { ( 𝐴𝑚 ) } → ( 𝑛 ∈ ( ( 𝐺 NeighbVtx 𝑚 ) ∩ 𝑁 ) ↔ 𝑛 ∈ { ( 𝐴𝑚 ) } ) )
58 57 eqcoms ( { ( 𝐴𝑚 ) } = ( ( 𝐺 NeighbVtx 𝑚 ) ∩ 𝑁 ) → ( 𝑛 ∈ ( ( 𝐺 NeighbVtx 𝑚 ) ∩ 𝑁 ) ↔ 𝑛 ∈ { ( 𝐴𝑚 ) } ) )
59 elsni ( 𝑛 ∈ { ( 𝐴𝑚 ) } → 𝑛 = ( 𝐴𝑚 ) )
60 58 59 syl6bi ( { ( 𝐴𝑚 ) } = ( ( 𝐺 NeighbVtx 𝑚 ) ∩ 𝑁 ) → ( 𝑛 ∈ ( ( 𝐺 NeighbVtx 𝑚 ) ∩ 𝑁 ) → 𝑛 = ( 𝐴𝑚 ) ) )
61 50 56 60 3syl ( ( 𝜑 ∧ { 𝑚 , 𝑋 } ∈ 𝐸 ) → ( 𝑛 ∈ ( ( 𝐺 NeighbVtx 𝑚 ) ∩ 𝑁 ) → 𝑛 = ( 𝐴𝑚 ) ) )
62 61 expcom ( { 𝑚 , 𝑋 } ∈ 𝐸 → ( 𝜑 → ( 𝑛 ∈ ( ( 𝐺 NeighbVtx 𝑚 ) ∩ 𝑁 ) → 𝑛 = ( 𝐴𝑚 ) ) ) )
63 62 com3r ( 𝑛 ∈ ( ( 𝐺 NeighbVtx 𝑚 ) ∩ 𝑁 ) → ( { 𝑚 , 𝑋 } ∈ 𝐸 → ( 𝜑𝑛 = ( 𝐴𝑚 ) ) ) )
64 48 63 sylbir ( ( 𝑛 ∈ ( 𝐺 NeighbVtx 𝑚 ) ∧ 𝑛𝑁 ) → ( { 𝑚 , 𝑋 } ∈ 𝐸 → ( 𝜑𝑛 = ( 𝐴𝑚 ) ) ) )
65 64 ex ( 𝑛 ∈ ( 𝐺 NeighbVtx 𝑚 ) → ( 𝑛𝑁 → ( { 𝑚 , 𝑋 } ∈ 𝐸 → ( 𝜑𝑛 = ( 𝐴𝑚 ) ) ) ) )
66 65 com14 ( 𝜑 → ( 𝑛𝑁 → ( { 𝑚 , 𝑋 } ∈ 𝐸 → ( 𝑛 ∈ ( 𝐺 NeighbVtx 𝑚 ) → 𝑛 = ( 𝐴𝑚 ) ) ) ) )
67 66 imp ( ( 𝜑𝑛𝑁 ) → ( { 𝑚 , 𝑋 } ∈ 𝐸 → ( 𝑛 ∈ ( 𝐺 NeighbVtx 𝑚 ) → 𝑛 = ( 𝐴𝑚 ) ) ) )
68 67 adantld ( ( 𝜑𝑛𝑁 ) → ( ( { 𝑛 , 𝑚 } ∈ 𝐸 ∧ { 𝑚 , 𝑋 } ∈ 𝐸 ) → ( 𝑛 ∈ ( 𝐺 NeighbVtx 𝑚 ) → 𝑛 = ( 𝐴𝑚 ) ) ) )
69 68 imp ( ( ( 𝜑𝑛𝑁 ) ∧ ( { 𝑛 , 𝑚 } ∈ 𝐸 ∧ { 𝑚 , 𝑋 } ∈ 𝐸 ) ) → ( 𝑛 ∈ ( 𝐺 NeighbVtx 𝑚 ) → 𝑛 = ( 𝐴𝑚 ) ) )
70 47 69 mpd ( ( ( 𝜑𝑛𝑁 ) ∧ ( { 𝑛 , 𝑚 } ∈ 𝐸 ∧ { 𝑚 , 𝑋 } ∈ 𝐸 ) ) → 𝑛 = ( 𝐴𝑚 ) )
71 40 70 jca ( ( ( 𝜑𝑛𝑁 ) ∧ ( { 𝑛 , 𝑚 } ∈ 𝐸 ∧ { 𝑚 , 𝑋 } ∈ 𝐸 ) ) → ( 𝑚𝐷𝑛 = ( 𝐴𝑚 ) ) )
72 71 ex ( ( 𝜑𝑛𝑁 ) → ( ( { 𝑛 , 𝑚 } ∈ 𝐸 ∧ { 𝑚 , 𝑋 } ∈ 𝐸 ) → ( 𝑚𝐷𝑛 = ( 𝐴𝑚 ) ) ) )
73 72 adantld ( ( 𝜑𝑛𝑁 ) → ( ( 𝑚𝑉 ∧ ( { 𝑛 , 𝑚 } ∈ 𝐸 ∧ { 𝑚 , 𝑋 } ∈ 𝐸 ) ) → ( 𝑚𝐷𝑛 = ( 𝐴𝑚 ) ) ) )
74 73 eximdv ( ( 𝜑𝑛𝑁 ) → ( ∃ 𝑚 ( 𝑚𝑉 ∧ ( { 𝑛 , 𝑚 } ∈ 𝐸 ∧ { 𝑚 , 𝑋 } ∈ 𝐸 ) ) → ∃ 𝑚 ( 𝑚𝐷𝑛 = ( 𝐴𝑚 ) ) ) )
75 32 74 mpd ( ( 𝜑𝑛𝑁 ) → ∃ 𝑚 ( 𝑚𝐷𝑛 = ( 𝐴𝑚 ) ) )
76 df-rex ( ∃ 𝑚𝐷 𝑛 = ( 𝐴𝑚 ) ↔ ∃ 𝑚 ( 𝑚𝐷𝑛 = ( 𝐴𝑚 ) ) )
77 75 76 sylibr ( ( 𝜑𝑛𝑁 ) → ∃ 𝑚𝐷 𝑛 = ( 𝐴𝑚 ) )
78 77 ralrimiva ( 𝜑 → ∀ 𝑛𝑁𝑚𝐷 𝑛 = ( 𝐴𝑚 ) )
79 dffo3 ( 𝐴 : 𝐷onto𝑁 ↔ ( 𝐴 : 𝐷𝑁 ∧ ∀ 𝑛𝑁𝑚𝐷 𝑛 = ( 𝐴𝑚 ) ) )
80 11 78 79 sylanbrc ( 𝜑𝐴 : 𝐷onto𝑁 )