eucrctshift - Metamath Proof Explorer

	Metamath Proof Explorer		< Previous Next > Nearby theorems
Mirrors > Home > MPE Home > Th. List > eucrctshift		Structured version Visualization version Unicode version

Theorem eucrctshift 27103

Description: Cyclically shifting the indices of an Eulerian circuit

results in an Eulerian circuit

. (Contributed by AV, 15-Mar-2021.) (Proof shortened by AV, 30-Oct-2021.)

**Hypotheses**
Ref	Expression
eucrctshift.v	Vtx
eucrctshift.i	iEdg
eucrctshift.c	Circuits
eucrctshift.n
eucrctshift.s	..^
eucrctshift.h	cyclShift
eucrctshift.q
eucrctshift.e	EulerPaths

**Assertion**
Ref	Expression
eucrctshift	EulerPaths $/\$ Circuits

Distinct variable groups:

Allowed substitution hints:

(

)

(

)

Proof of Theorem eucrctshift Dummy variables

are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		eucrctshift.v	. . . . 5 Vtx
2		eucrctshift.i	. . . . 5 iEdg
3		eucrctshift.c	. . . . 5 Circuits
4		eucrctshift.n	. . . . 5
5		eucrctshift.s	. . . . 5 ..^
6		eucrctshift.h	. . . . 5 cyclShift
7		eucrctshift.q	. . . . 5
8	1, 2, 3, 4, 5, 6, 7	crctcshtrl 26715	. . . 4 Trails
9		simpr 477	. . . . 5 $/\$ Trails Trails
10		eucrctshift.e	. . . . . . . 8 EulerPaths
11	2	eupthf1o 27064	. . . . . . . 8 EulerPaths ..^
12	10, 11	syl 17	. . . . . . 7 ..^
13	12	adantr 481	. . . . . 6 $/\$ Trails ..^
14		trliswlk 26594	. . . . . . . . 9 Trails Walks
15	2	wlkf 26510	. . . . . . . . 9 Walks Word
16		wrdf 13310	. . . . . . . . 9 Word ..^
17	14, 15, 16	3syl 18	. . . . . . . 8 Trails ..^
18		df-f1o 5895	. . . . . . . . . 10 ..^ ..^ $/\$ ..^
19		dffo3 6374	. . . . . . . . . . 11 ..^ ..^ $/\$ ..^
20		crctiswlk 26691	. . . . . . . . . . . . . . . . . . . . . . . . . . 27 Circuits Walks
21	2	wlkf 26510	. . . . . . . . . . . . . . . . . . . . . . . . . . 27 Walks Word
22		lencl 13324	. . . . . . . . . . . . . . . . . . . . . . . . . . . 28 Word
23	4	oveq2i 6661	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 ..^ ..^
24	23	eleq2i 2693	. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ..^ ..^
25		elfzonn0 12512	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 ..^
26	25	adantl 482	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 $/\$ ..^
27		elfzonn0 12512	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 ..^
28		nn0sub 11343	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 $/\$
29	26, 27, 28	syl2an 494	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 $/\$ ..^ $/\$ ..^
30	29	biimpac 503	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 $/\$ $/\$ ..^ $/\$ ..^
31		elfzo0 12508	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 ..^ $/\$ $/\$
32		simp2 1062	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 $/\$ $/\$
33	31, 32	sylbi 207	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 ..^
34	33	ad2antll 765	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 $/\$ $/\$ ..^ $/\$ ..^
35		nn0re 11301	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
36	35	ad2antrr 762	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 $/\$ $/\$ ..^
37		nnre 11027	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
38	37	adantl 482	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 $/\$
39	38	adantr 481	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 $/\$ $/\$ ..^
40		elfzoelz 12470	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 ..^
41	40	zred 11482	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 ..^
42		readdcl 10019	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 $/\$
43	38, 41, 42	syl2an 494	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 $/\$ $/\$ ..^
44	36, 39, 43	3jca 1242	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 $/\$ $/\$ ..^ $/\$ $/\$
45		elfzole1 12478	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 ..^
46	45	adantl 482	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 $/\$ $/\$ ..^
47		addge01 10538	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 $/\$
48	38, 41, 47	syl2an 494	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 $/\$ $/\$ ..^
49	46, 48	mpbid 222	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 $/\$ $/\$ ..^
50	44, 49	lelttrdi 10199	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 $/\$ $/\$ ..^
51	50	ex 450	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 $/\$ ..^
52	51	com23 86	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 $/\$ ..^
53	52	3impia 1261	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 $/\$ $/\$ ..^
54	53	adantld 483	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 $/\$ $/\$ $/\$ ..^
55	54	imp 445	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 $/\$ $/\$ $/\$ $/\$ ..^
56	35	3ad2ant1 1082	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 $/\$ $/\$
57	56	adantr 481	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 $/\$ $/\$ $/\$ $/\$ ..^
58	41	ad2antll 765	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 $/\$ $/\$ $/\$ $/\$ ..^
59		elfzoel2 12469	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 ..^
60	59	zred 11482	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 ..^
61	60	ad2antll 765	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 $/\$ $/\$ $/\$ $/\$ ..^
62	57, 58, 61	ltsubaddd 10623	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 $/\$ $/\$ $/\$ $/\$ ..^
63	55, 62	mpbird 247	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 $/\$ $/\$ $/\$ $/\$ ..^
64	63	ex 450	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 $/\$ $/\$ $/\$ ..^
65	31, 64	sylbi 207	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 ..^ $/\$ ..^
66	65	impcom 446	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 $/\$ ..^ $/\$ ..^
67	66	adantl 482	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 $/\$ $/\$ ..^ $/\$ ..^
68		elfzo0 12508	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 ..^ $/\$ $/\$
69	30, 34, 67, 68	syl3anbrc 1246	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 $/\$ $/\$ ..^ $/\$ ..^ ..^
70		oveq1 6657	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
71	70	oveq1d 6665	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
72	40	zcnd 11483	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 ..^
73	72	adantl 482	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 $/\$ ..^
74		elfzoelz 12470	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 ..^
75	74	zcnd 11483	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 ..^
76	73, 75	anim12ci 591	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 $/\$ ..^ $/\$ ..^ $/\$
77	76	adantl 482	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 $/\$ $/\$ ..^ $/\$ ..^ $/\$
78		npcan 10290	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 $/\$
79	77, 78	syl 17	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 $/\$ $/\$ ..^ $/\$ ..^
80	79	oveq1d 6665	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 $/\$ $/\$ ..^ $/\$ ..^
81		zmodidfzoimp 12700	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 ..^
82	81	ad2antll 765	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 $/\$ $/\$ ..^ $/\$ ..^
83	80, 82	eqtrd 2656	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 $/\$ $/\$ ..^ $/\$ ..^
84	71, 83	sylan9eqr 2678	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 $/\$ $/\$ ..^ $/\$ ..^ $/\$
85	84	eqcomd 2628	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 $/\$ $/\$ ..^ $/\$ ..^ $/\$
86	69, 85	rspcedeq2vd 3319	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 $/\$ $/\$ ..^ $/\$ ..^ ..^
87		elfzo0 12508	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 ..^ $/\$ $/\$
88		nn0cn 11302	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
89	88	ad2antrr 762	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 $/\$ $/\$ $/\$ $/\$
90		nn0cn 11302	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
91	90	3ad2ant1 1082	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 $/\$ $/\$
92	91	adantl 482	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 $/\$ $/\$ $/\$ $/\$
93		nncn 11028	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
94	93	3ad2ant2 1083	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 $/\$ $/\$
95	94	adantl 482	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 $/\$ $/\$ $/\$ $/\$
96	89, 92, 95	subadd23d 10414	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 $/\$ $/\$ $/\$ $/\$
97		simpll 790	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 $/\$ $/\$ $/\$ $/\$
98		nn0z 11400	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
99		nnz 11399	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
100		znnsub 11423	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 $/\$
101	98, 99, 100	syl2an 494	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 $/\$
102	101	biimp3a 1432	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 $/\$ $/\$
103	102	adantl 482	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 $/\$ $/\$ $/\$ $/\$
104	103	nnnn0d 11351	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 $/\$ $/\$ $/\$ $/\$
105	97, 104	nn0addcld 11355	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 $/\$ $/\$ $/\$ $/\$
106	96, 105	eqeltrd 2701	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 $/\$ $/\$ $/\$ $/\$
107	106	adantr 481	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 $/\$ $/\$ $/\$ $/\$ $/\$
108		simplr2 1104	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 $/\$ $/\$ $/\$ $/\$ $/\$
109	88	adantr 481	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 $/\$
110		subcl 10280	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 $/\$
111	109, 91, 110	syl2an 494	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 $/\$ $/\$ $/\$ $/\$
112	95, 111	jca 554	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 $/\$ $/\$ $/\$ $/\$ $/\$
113	112	adantr 481	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 $/\$ $/\$ $/\$ $/\$ $/\$ $/\$
114		addcom 10222	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 $/\$
115	113, 114	syl 17	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 $/\$ $/\$ $/\$ $/\$ $/\$
116	35	adantr 481	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 $/\$
117		nn0re 11301	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
118	117	3ad2ant1 1082	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 $/\$ $/\$
119		ltnle 10117	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 $/\$
120		simpl 473	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 $/\$
121		simpr 477	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 $/\$
122	120, 121	sublt0d 10653	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 $/\$
123	122	biimprd 238	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 $/\$
124	119, 123	sylbird 250	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 $/\$
125	116, 118, 124	syl2an 494	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 $/\$ $/\$ $/\$ $/\$
126	125	imp 445	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 $/\$ $/\$ $/\$ $/\$ $/\$
127		resubcl 10345	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 $/\$
128	116, 118, 127	syl2an 494	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 $/\$ $/\$ $/\$ $/\$
129	37	3ad2ant2 1083	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 $/\$ $/\$
130	129	adantl 482	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 $/\$ $/\$ $/\$ $/\$
131	128, 130	jca 554	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 $/\$ $/\$ $/\$ $/\$ $/\$
132	131	adantr 481	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 $/\$ $/\$ $/\$ $/\$ $/\$ $/\$
133		ltaddneg 10251	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 $/\$
134	132, 133	syl 17	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 $/\$ $/\$ $/\$ $/\$ $/\$
135	126, 134	mpbid 222	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 $/\$ $/\$ $/\$ $/\$ $/\$
136	115, 135	eqbrtrrd 4677	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 $/\$ $/\$ $/\$ $/\$ $/\$
137	107, 108, 136	3jca 1242	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 $/\$ $/\$ $/\$ $/\$ $/\$ $/\$ $/\$
138	137	exp31 630	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 $/\$ $/\$ $/\$ $/\$ $/\$
139	138	3adant2 1080	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 $/\$ $/\$ $/\$ $/\$ $/\$ $/\$
140	87, 139	syl5bi 232	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 $/\$ $/\$ ..^ $/\$ $/\$
141	140	adantld 483	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 $/\$ $/\$ $/\$ ..^ $/\$ $/\$
142	31, 141	sylbi 207	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 ..^ $/\$ ..^ $/\$ $/\$
143	142	impcom 446	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 $/\$ ..^ $/\$ ..^ $/\$ $/\$
144	143	impcom 446	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 $/\$ $/\$ ..^ $/\$ ..^ $/\$ $/\$
145		elfzo0 12508	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 ..^ $/\$ $/\$
146	144, 145	sylibr 224	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 $/\$ $/\$ ..^ $/\$ ..^ ..^
147		oveq1 6657	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
148	147	oveq1d 6665	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
149	73	adantr 481	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 $/\$ ..^ $/\$ ..^
150	75	adantl 482	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 $/\$ ..^ $/\$ ..^
151		nn0cn 11302	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
152	151	ad2antrr 762	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 $/\$ ..^ $/\$ ..^
153	149, 150, 152	3jca 1242	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 $/\$ ..^ $/\$ ..^ $/\$ $/\$
154	153	adantl 482	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 $/\$ $/\$ ..^ $/\$ ..^ $/\$ $/\$
155		simp2 1062	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 $/\$ $/\$
156		simp3 1063	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 $/\$ $/\$
157		simp1 1061	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 $/\$ $/\$
158	155, 157, 156	nppcand 10417	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 $/\$ $/\$
159	155, 156, 158	comraddd 10250	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 $/\$ $/\$
160	154, 159	syl 17	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 $/\$ $/\$ ..^ $/\$ ..^
161	160	oveq1d 6665	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 $/\$ $/\$ ..^ $/\$ ..^
162	31	biimpi 206	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 ..^ $/\$ $/\$
163	162	ad2antll 765	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 $/\$ $/\$ ..^ $/\$ ..^ $/\$ $/\$
164		addmodid 12718	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 $/\$ $/\$
165	163, 164	syl 17	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 $/\$ $/\$ ..^ $/\$ ..^
166	161, 165	eqtrd 2656	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 $/\$ $/\$ ..^ $/\$ ..^
167	148, 166	sylan9eqr 2678	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 $/\$ $/\$ ..^ $/\$ ..^ $/\$
168	167	eqcomd 2628	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 $/\$ $/\$ ..^ $/\$ ..^ $/\$
169	146, 168	rspcedeq2vd 3319	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 $/\$ $/\$ ..^ $/\$ ..^ ..^
170	86, 169	pm2.61ian 831	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 $/\$ ..^ $/\$ ..^ ..^
171	23	rexeqi 3143	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 ..^ ..^
172	170, 171	sylibr 224	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 $/\$ ..^ $/\$ ..^ ..^
173	172	exp31 630	. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ..^ ..^ ..^
174	24, 173	syl5bi 232	. . . . . . . . . . . . . . . . . . . . . . . . . . . 28 ..^ ..^ ..^
175	22, 174	syl 17	. . . . . . . . . . . . . . . . . . . . . . . . . . 27 Word ..^ ..^ ..^
176	20, 21, 175	3syl 18	. . . . . . . . . . . . . . . . . . . . . . . . . 26 Circuits ..^ ..^ ..^
177	3, 5, 176	sylc 65	. . . . . . . . . . . . . . . . . . . . . . . . 25 ..^ ..^
178	177	adantr 481	. . . . . . . . . . . . . . . . . . . . . . . 24 $/\$ ..^ ..^
179	178	imp 445	. . . . . . . . . . . . . . . . . . . . . . 23 $/\$ $/\$ ..^ ..^
180	179	adantr 481	. . . . . . . . . . . . . . . . . . . . . 22 $/\$ $/\$ ..^ $/\$ ..^
181		fveq2 6191	. . . . . . . . . . . . . . . . . . . . . . 23
182	181	reximi 3011	. . . . . . . . . . . . . . . . . . . . . 22 ..^ ..^
183	180, 182	syl 17	. . . . . . . . . . . . . . . . . . . . 21 $/\$ $/\$ ..^ $/\$ ..^
184	3, 20, 21	3syl 18	. . . . . . . . . . . . . . . . . . . . . . . . 25 Word
185	184	ad3antrrr 766	. . . . . . . . . . . . . . . . . . . . . . . 24 $/\$ $/\$ ..^ $/\$ Word
186		elfzoelz 12470	. . . . . . . . . . . . . . . . . . . . . . . . . 26 ..^
187	5, 186	syl 17	. . . . . . . . . . . . . . . . . . . . . . . . 25
188	187	ad3antrrr 766	. . . . . . . . . . . . . . . . . . . . . . . 24 $/\$ $/\$ ..^ $/\$
189	23	eleq2i 2693	. . . . . . . . . . . . . . . . . . . . . . . . 25 ..^ ..^
190	189	biimpi 206	. . . . . . . . . . . . . . . . . . . . . . . 24 ..^ ..^
191		cshwidxmod 13549	. . . . . . . . . . . . . . . . . . . . . . . 24 Word $/\$ $/\$ ..^ cyclShift
192	185, 188, 190, 191	syl2an3an 1386	. . . . . . . . . . . . . . . . . . . . . . 23 $/\$ $/\$ ..^ $/\$ $/\$ ..^ cyclShift
193	192	eqeq2d 2632	. . . . . . . . . . . . . . . . . . . . . 22 $/\$ $/\$ ..^ $/\$ $/\$ ..^ cyclShift
194	193	rexbidva 3049	. . . . . . . . . . . . . . . . . . . . 21 $/\$ $/\$ ..^ $/\$ ..^ cyclShift ..^
195	183, 194	mpbird 247	. . . . . . . . . . . . . . . . . . . 20 $/\$ $/\$ ..^ $/\$ ..^ cyclShift
196	1, 2, 3, 4, 5, 6	crctcshlem2 26710	. . . . . . . . . . . . . . . . . . . . . . 23
197	196	oveq2d 6666	. . . . . . . . . . . . . . . . . . . . . 22 ..^ ..^
198	197	ad3antrrr 766	. . . . . . . . . . . . . . . . . . . . 21 $/\$ $/\$ ..^ $/\$ ..^ ..^
199		simpr 477	. . . . . . . . . . . . . . . . . . . . . 22 $/\$ $/\$ ..^ $/\$
200	6	fveq1i 6192	. . . . . . . . . . . . . . . . . . . . . . 23 cyclShift
201	200	a1i 11	. . . . . . . . . . . . . . . . . . . . . 22 $/\$ $/\$ ..^ $/\$ cyclShift
202	199, 201	eqeq12d 2637	. . . . . . . . . . . . . . . . . . . . 21 $/\$ $/\$ ..^ $/\$ cyclShift
203	198, 202	rexeqbidv 3153	. . . . . . . . . . . . . . . . . . . 20 $/\$ $/\$ ..^ $/\$ ..^ ..^ cyclShift
204	195, 203	mpbird 247	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$ ..^ $/\$ ..^
205	204	ex 450	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$ ..^ ..^
206	205	rexlimdva 3031	. . . . . . . . . . . . . . . . 17 $/\$ ..^ ..^
207	206	ralimdva 2962	. . . . . . . . . . . . . . . 16 ..^ ..^
208	207	impcom 446	. . . . . . . . . . . . . . 15 ..^ $/\$ ..^
209	208	anim1i 592	. . . . . . . . . . . . . 14 ..^ $/\$ $/\$ ..^ ..^ $/\$ ..^
210	209	ancomd 467	. . . . . . . . . . . . 13 ..^ $/\$ $/\$ ..^ ..^ $/\$ ..^
211		dffo3 6374	. . . . . . . . . . . . 13 ..^ ..^ $/\$ ..^
212	210, 211	sylibr 224	. . . . . . . . . . . 12 ..^ $/\$ $/\$ ..^ ..^
213	212	exp31 630	. . . . . . . . . . 11 ..^ ..^ ..^
214	19, 213	simplbiim 659	. . . . . . . . . 10 ..^ ..^ ..^
215	18, 214	simplbiim 659	. . . . . . . . 9 ..^ ..^ ..^
216	215	com13 88	. . . . . . . 8 ..^ ..^ ..^
217	17, 216	syl 17	. . . . . . 7 Trails ..^ ..^
218	217	impcom 446	. . . . . 6 $/\$ Trails ..^ ..^
219	13, 218	mpd 15	. . . . 5 $/\$ Trails ..^
220	9, 219	jca 554	. . . 4 $/\$ Trails Trails $/\$ ..^
221	8, 220	mpdan 702	. . 3 Trails $/\$ ..^
222	2	iseupth 27061	. . 3 EulerPaths Trails $/\$ ..^
223	221, 222	sylibr 224	. 2 EulerPaths
224	1, 2, 3, 4, 5, 6, 7	crctcsh 26716	. 2 Circuits
225	223, 224	jca 554	1 EulerPaths $/\$ Circuits

Colors of variables: wff setvar class

Syntax hints:

wn 3

wi 4

wb 196 $/\$ wa 384 $/\$ w3a 1037

wceq 1483

wcel 1990

wral 2912

wrex 2913

cif 4086 class class class wbr 4653

cmpt 4729

cdm 5114

wf 5884

wf1 5885

wfo 5886

wf1o 5887

cfv 5888 (class class class)co 6650

cc 9934

cr 9935

cc0 9936

caddc 9939

clt 10074

cle 10075

cmin 10266

cn 11020

cn0 11292

cz 11377

cfz 12326 ..^cfzo 12465

cmo 12668

chash 13117 Word cword 13291 cyclShift ccsh 13534 Vtxcvtx 25874 iEdgciedg 25875 Walkscwlks 26492 Trailsctrls 26587 Circuitsccrcts 26679 EulerPathsceupth 27057

This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1722 ax-4 1737 ax-5 1839 ax-6 1888 ax-7 1935 ax-8 1992 ax-9 1999 ax-10 2019 ax-11 2034 ax-12 2047 ax-13 2246 ax-ext 2602 ax-rep 4771 ax-sep 4781 ax-nul 4789 ax-pow 4843 ax-pr 4906 ax-un 6949 ax-cnex 9992 ax-resscn 9993 ax-1cn 9994 ax-icn 9995 ax-addcl 9996 ax-addrcl 9997 ax-mulcl 9998 ax-mulrcl 9999 ax-mulcom 10000 ax-addass 10001 ax-mulass 10002 ax-distr 10003 ax-i2m1 10004 ax-1ne0 10005 ax-1rid 10006 ax-rnegex 10007 ax-rrecex 10008 ax-cnre 10009 ax-pre-lttri 10010 ax-pre-lttrn 10011 ax-pre-ltadd 10012 ax-pre-mulgt0 10013 ax-pre-sup 10014

This theorem depends on definitions: df-bi 197 df-or 385 df-an 386 df-ifp 1013 df-3or 1038 df-3an 1039 df-tru 1486 df-ex 1705 df-nf 1710 df-sb 1881 df-eu 2474 df-mo 2475 df-clab 2609 df-cleq 2615 df-clel 2618 df-nfc 2753 df-ne 2795 df-nel 2898 df-ral 2917 df-rex 2918 df-reu 2919 df-rmo 2920 df-rab 2921 df-v 3202 df-sbc 3436 df-csb 3534 df-dif 3577 df-un 3579 df-in 3581 df-ss 3588 df-pss 3590 df-nul 3916 df-if 4087 df-pw 4160 df-sn 4178 df-pr 4180 df-tp 4182 df-op 4184 df-uni 4437 df-int 4476 df-iun 4522 df-br 4654 df-opab 4713 df-mpt 4730 df-tr 4753 df-id 5024 df-eprel 5029 df-po 5035 df-so 5036 df-fr 5073 df-we 5075 df-xp 5120 df-rel 5121 df-cnv 5122 df-co 5123 df-dm 5124 df-rn 5125 df-res 5126 df-ima 5127 df-pred 5680 df-ord 5726 df-on 5727 df-lim 5728 df-suc 5729 df-iota 5851 df-fun 5890 df-fn 5891 df-f 5892 df-f1 5893 df-fo 5894 df-f1o 5895 df-fv 5896 df-riota 6611 df-ov 6653 df-oprab 6654 df-mpt2 6655 df-om 7066 df-1st 7168 df-2nd 7169 df-wrecs 7407 df-recs 7468 df-rdg 7506 df-1o 7560 df-oadd 7564 df-er 7742 df-map 7859 df-pm 7860 df-en 7956 df-dom 7957 df-sdom 7958 df-fin 7959 df-sup 8348 df-inf 8349 df-card 8765 df-pnf 10076 df-mnf 10077 df-xr 10078 df-ltxr 10079 df-le 10080 df-sub 10268 df-neg 10269 df-div 10685 df-nn 11021 df-2 11079 df-n0 11293 df-z 11378 df-uz 11688 df-rp 11833 df-ico 12181 df-fz 12327 df-fzo 12466 df-fl 12593 df-mod 12669 df-hash 13118 df-word 13299 df-concat 13301 df-substr 13303 df-csh 13535 df-wlks 26495 df-trls 26589 df-crcts 26681 df-eupth 27058

This theorem is referenced by: eucrct2eupth 27105

W3C validator