Metamath Proof Explorer

Theorem cusgracyclt3v

Description: A complete simple graph is acyclic if and only if it has fewer than three vertices. (Contributed by BTernaryTau, 20-Oct-2023)

Ref Expression
Hypothesis cusgracyclt3v.1 
|- V = ( Vtx ` G )
Assertion cusgracyclt3v 
|- ( G e. ComplUSGraph -> ( G e. AcyclicGraph <-> ( # ` V ) < 3 ) )

Proof

Step Hyp Ref Expression
1 cusgracyclt3v.1 
 |-  V = ( Vtx ` G )
2 isacycgr 
 |-  ( G e. ComplUSGraph -> ( G e. AcyclicGraph <-> -. E. f E. p ( f ( Cycles ` G ) p /\ f =/= (/) ) ) )
3 3nn0 
 |-  3 e. NN0
4 1 fvexi 
 |-  V e. _V
5 hashxnn0 
 |-  ( V e. _V -> ( # ` V ) e. NN0* )
6 4 5 ax-mp 
 |-  ( # ` V ) e. NN0*
7 xnn0lem1lt 
 |-  ( ( 3 e. NN0 /\ ( # ` V ) e. NN0* ) -> ( 3 <_ ( # ` V ) <-> ( 3 - 1 ) < ( # ` V ) ) )
8 3 6 7 mp2an 
 |-  ( 3 <_ ( # ` V ) <-> ( 3 - 1 ) < ( # ` V ) )
9 3re 
 |-  3 e. RR
10 9 rexri 
 |-  3 e. RR*
11 xnn0xr 
 |-  ( ( # ` V ) e. NN0* -> ( # ` V ) e. RR* )
12 6 11 ax-mp 
 |-  ( # ` V ) e. RR*
13 xrlenlt 
 |-  ( ( 3 e. RR* /\ ( # ` V ) e. RR* ) -> ( 3 <_ ( # ` V ) <-> -. ( # ` V ) < 3 ) )
14 10 12 13 mp2an 
 |-  ( 3 <_ ( # ` V ) <-> -. ( # ` V ) < 3 )
15 3m1e2 
 |-  ( 3 - 1 ) = 2
16 15 breq1i 
 |-  ( ( 3 - 1 ) < ( # ` V ) <-> 2 < ( # ` V ) )
17 8 14 16 3bitr3i 
 |-  ( -. ( # ` V ) < 3 <-> 2 < ( # ` V ) )
18 1 cusgr3cyclex 
 |-  ( ( G e. ComplUSGraph /\ 2 < ( # ` V ) ) -> E. f E. p ( f ( Cycles ` G ) p /\ ( # ` f ) = 3 ) )
19 3ne0 
 |-  3 =/= 0
20 neeq1 
 |-  ( ( # ` f ) = 3 -> ( ( # ` f ) =/= 0 <-> 3 =/= 0 ) )
21 19 20 mpbiri 
 |-  ( ( # ` f ) = 3 -> ( # ` f ) =/= 0 )
22 hasheq0 
 |-  ( f e. _V -> ( ( # ` f ) = 0 <-> f = (/) ) )
23 22 elv 
 |-  ( ( # ` f ) = 0 <-> f = (/) )
24 23 necon3bii 
 |-  ( ( # ` f ) =/= 0 <-> f =/= (/) )
25 21 24 sylib 
 |-  ( ( # ` f ) = 3 -> f =/= (/) )
26 25 anim2i 
 |-  ( ( f ( Cycles ` G ) p /\ ( # ` f ) = 3 ) -> ( f ( Cycles ` G ) p /\ f =/= (/) ) )
27 26 2eximi 
 |-  ( E. f E. p ( f ( Cycles ` G ) p /\ ( # ` f ) = 3 ) -> E. f E. p ( f ( Cycles ` G ) p /\ f =/= (/) ) )
28 18 27 syl 
 |-  ( ( G e. ComplUSGraph /\ 2 < ( # ` V ) ) -> E. f E. p ( f ( Cycles ` G ) p /\ f =/= (/) ) )
29 28 ex 
 |-  ( G e. ComplUSGraph -> ( 2 < ( # ` V ) -> E. f E. p ( f ( Cycles ` G ) p /\ f =/= (/) ) ) )
30 17 29 biimtrid 
 |-  ( G e. ComplUSGraph -> ( -. ( # ` V ) < 3 -> E. f E. p ( f ( Cycles ` G ) p /\ f =/= (/) ) ) )
31 30 con1d 
 |-  ( G e. ComplUSGraph -> ( -. E. f E. p ( f ( Cycles ` G ) p /\ f =/= (/) ) -> ( # ` V ) < 3 ) )
32 2 31 sylbid 
 |-  ( G e. ComplUSGraph -> ( G e. AcyclicGraph -> ( # ` V ) < 3 ) )
33 cusgrusgr 
 |-  ( G e. ComplUSGraph -> G e. USGraph )
34 1 usgrcyclgt2v 
 |-  ( ( G e. USGraph /\ f ( Cycles ` G ) p /\ f =/= (/) ) -> 2 < ( # ` V ) )
35 34 3expib 
 |-  ( G e. USGraph -> ( ( f ( Cycles ` G ) p /\ f =/= (/) ) -> 2 < ( # ` V ) ) )
36 33 35 syl 
 |-  ( G e. ComplUSGraph -> ( ( f ( Cycles ` G ) p /\ f =/= (/) ) -> 2 < ( # ` V ) ) )
37 36 17 imbitrrdi 
 |-  ( G e. ComplUSGraph -> ( ( f ( Cycles ` G ) p /\ f =/= (/) ) -> -. ( # ` V ) < 3 ) )
38 37 exlimdvv 
 |-  ( G e. ComplUSGraph -> ( E. f E. p ( f ( Cycles ` G ) p /\ f =/= (/) ) -> -. ( # ` V ) < 3 ) )
39 38 con2d 
 |-  ( G e. ComplUSGraph -> ( ( # ` V ) < 3 -> -. E. f E. p ( f ( Cycles ` G ) p /\ f =/= (/) ) ) )
40 39 2 sylibrd 
 |-  ( G e. ComplUSGraph -> ( ( # ` V ) < 3 -> G e. AcyclicGraph ) )
41 32 40 impbid 
 |-  ( G e. ComplUSGraph -> ( G e. AcyclicGraph <-> ( # ` V ) < 3 ) )