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
|
syl5bi |
|- ( 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
|
syl6ibr |
|- ( 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 ) ) |