Theorem subgrpth

Description: If a path exists in a subgraph of a graph G , then that path also exists in G . (Contributed by BTernaryTau, 22-Oct-2023)

	Ref	Expression
Assertion	subgrpth	⊢ ( 𝑆 SubGraph 𝐺 → ( 𝐹 ( Paths ‘ 𝑆 ) 𝑃 → 𝐹 ( Paths ‘ 𝐺 ) 𝑃 ) )

Proof

Step	Hyp	Ref	Expression
1		subgrtrl	⊢ ( 𝑆 SubGraph 𝐺 → ( 𝐹 ( Trails ‘ 𝑆 ) 𝑃 → 𝐹 ( Trails ‘ 𝐺 ) 𝑃 ) )
2		idd	⊢ ( 𝑆 SubGraph 𝐺 → ( Fun ◡ ( 𝑃 ↾ ( 1 ..^ ( ♯ ‘ 𝐹 ) ) ) → Fun ◡ ( 𝑃 ↾ ( 1 ..^ ( ♯ ‘ 𝐹 ) ) ) ) )
3		idd	⊢ ( 𝑆 SubGraph 𝐺 → ( ( ( 𝑃 “ { 0 , ( ♯ ‘ 𝐹 ) } ) ∩ ( 𝑃 “ ( 1 ..^ ( ♯ ‘ 𝐹 ) ) ) ) = ∅ → ( ( 𝑃 “ { 0 , ( ♯ ‘ 𝐹 ) } ) ∩ ( 𝑃 “ ( 1 ..^ ( ♯ ‘ 𝐹 ) ) ) ) = ∅ ) )
4	1 2 3	3anim123d	⊢ ( 𝑆 SubGraph 𝐺 → ( ( 𝐹 ( Trails ‘ 𝑆 ) 𝑃 ∧ Fun ◡ ( 𝑃 ↾ ( 1 ..^ ( ♯ ‘ 𝐹 ) ) ) ∧ ( ( 𝑃 “ { 0 , ( ♯ ‘ 𝐹 ) } ) ∩ ( 𝑃 “ ( 1 ..^ ( ♯ ‘ 𝐹 ) ) ) ) = ∅ ) → ( 𝐹 ( Trails ‘ 𝐺 ) 𝑃 ∧ Fun ◡ ( 𝑃 ↾ ( 1 ..^ ( ♯ ‘ 𝐹 ) ) ) ∧ ( ( 𝑃 “ { 0 , ( ♯ ‘ 𝐹 ) } ) ∩ ( 𝑃 “ ( 1 ..^ ( ♯ ‘ 𝐹 ) ) ) ) = ∅ ) ) )
5		ispth	⊢ ( 𝐹 ( Paths ‘ 𝑆 ) 𝑃 ↔ ( 𝐹 ( Trails ‘ 𝑆 ) 𝑃 ∧ Fun ◡ ( 𝑃 ↾ ( 1 ..^ ( ♯ ‘ 𝐹 ) ) ) ∧ ( ( 𝑃 “ { 0 , ( ♯ ‘ 𝐹 ) } ) ∩ ( 𝑃 “ ( 1 ..^ ( ♯ ‘ 𝐹 ) ) ) ) = ∅ ) )
6		ispth	⊢ ( 𝐹 ( Paths ‘ 𝐺 ) 𝑃 ↔ ( 𝐹 ( Trails ‘ 𝐺 ) 𝑃 ∧ Fun ◡ ( 𝑃 ↾ ( 1 ..^ ( ♯ ‘ 𝐹 ) ) ) ∧ ( ( 𝑃 “ { 0 , ( ♯ ‘ 𝐹 ) } ) ∩ ( 𝑃 “ ( 1 ..^ ( ♯ ‘ 𝐹 ) ) ) ) = ∅ ) )
7	4 5 6	3imtr4g	⊢ ( 𝑆 SubGraph 𝐺 → ( 𝐹 ( Paths ‘ 𝑆 ) 𝑃 → 𝐹 ( Paths ‘ 𝐺 ) 𝑃 ) )