Metamath Proof Explorer

Theorem isubgr3stgr

Description: If a vertex of a simple graph has exactly N (different) neighbors, and none of these neighbors are connected by an edge, then the (closed) neighborhood of this vertex induces a subgraph which is isomorphic to an N-star. (Contributed by AV, 29-Sep-2025)

Ref Expression
Hypotheses isubgr3stgr.v 
|- V = ( Vtx ` G )
isubgr3stgr.u 
|- U = ( G NeighbVtx X )
isubgr3stgr.c 
|- C = ( G ClNeighbVtx X )
isubgr3stgr.n 
|- N e. NN0
isubgr3stgr.s 
|- S = ( StarGr ` N )
isubgr3stgr.w 
|- W = ( Vtx ` S )
isubgr3stgr.e 
|- E = ( Edg ` G )
Assertion isubgr3stgr 
|- ( ( G e. USGraph /\ X e. V ) -> ( ( ( # ` U ) = N /\ A. x e. U A. y e. U { x , y } e/ E ) -> ( G ISubGr C ) ~=gr ( StarGr ` N ) ) )

Proof

Step Hyp Ref Expression
1 isubgr3stgr.v 
 |-  V = ( Vtx ` G )
2 isubgr3stgr.u 
 |-  U = ( G NeighbVtx X )
3 isubgr3stgr.c 
 |-  C = ( G ClNeighbVtx X )
4 isubgr3stgr.n 
 |-  N e. NN0
5 isubgr3stgr.s 
 |-  S = ( StarGr ` N )
6 isubgr3stgr.w 
 |-  W = ( Vtx ` S )
7 isubgr3stgr.e 
 |-  E = ( Edg ` G )
8 simpl 
 |-  ( ( G e. USGraph /\ X e. V ) -> G e. USGraph )
9 simpr 
 |-  ( ( G e. USGraph /\ X e. V ) -> X e. V )
10 simpl 
 |-  ( ( ( # ` U ) = N /\ A. x e. U A. y e. U { x , y } e/ E ) -> ( # ` U ) = N )
11 1 2 3 4 5 6 isubgr3stgrlem3 
 |-  ( ( G e. USGraph /\ X e. V /\ ( # ` U ) = N ) -> E. f ( f : C -1-1-onto-> W /\ ( f ` X ) = 0 ) )
12 8 9 10 11 syl2an3an 
 |-  ( ( ( G e. USGraph /\ X e. V ) /\ ( ( # ` U ) = N /\ A. x e. U A. y e. U { x , y } e/ E ) ) -> E. f ( f : C -1-1-onto-> W /\ ( f ` X ) = 0 ) )
13 1 clnbgrssvtx 
 |-  ( G ClNeighbVtx X ) C_ V
14 3 13 eqsstri 
 |-  C C_ V
15 14 a1i 
 |-  ( X e. V -> C C_ V )
16 15 anim2i 
 |-  ( ( G e. USGraph /\ X e. V ) -> ( G e. USGraph /\ C C_ V ) )
17 16 adantr 
 |-  ( ( ( G e. USGraph /\ X e. V ) /\ ( ( # ` U ) = N /\ A. x e. U A. y e. U { x , y } e/ E ) ) -> ( G e. USGraph /\ C C_ V ) )
18 1 isubgrvtx 
 |-  ( ( G e. USGraph /\ C C_ V ) -> ( Vtx ` ( G ISubGr C ) ) = C )
19 17 18 syl 
 |-  ( ( ( G e. USGraph /\ X e. V ) /\ ( ( # ` U ) = N /\ A. x e. U A. y e. U { x , y } e/ E ) ) -> ( Vtx ` ( G ISubGr C ) ) = C )
20 19 eqcomd 
 |-  ( ( ( G e. USGraph /\ X e. V ) /\ ( ( # ` U ) = N /\ A. x e. U A. y e. U { x , y } e/ E ) ) -> C = ( Vtx ` ( G ISubGr C ) ) )
21 20 f1oeq2d 
 |-  ( ( ( G e. USGraph /\ X e. V ) /\ ( ( # ` U ) = N /\ A. x e. U A. y e. U { x , y } e/ E ) ) -> ( f : C -1-1-onto-> W <-> f : ( Vtx ` ( G ISubGr C ) ) -1-1-onto-> W ) )
22 21 biimpd 
 |-  ( ( ( G e. USGraph /\ X e. V ) /\ ( ( # ` U ) = N /\ A. x e. U A. y e. U { x , y } e/ E ) ) -> ( f : C -1-1-onto-> W -> f : ( Vtx ` ( G ISubGr C ) ) -1-1-onto-> W ) )
23 22 adantrd 
 |-  ( ( ( G e. USGraph /\ X e. V ) /\ ( ( # ` U ) = N /\ A. x e. U A. y e. U { x , y } e/ E ) ) -> ( ( f : C -1-1-onto-> W /\ ( f ` X ) = 0 ) -> f : ( Vtx ` ( G ISubGr C ) ) -1-1-onto-> W ) )
24 23 imp 
 |-  ( ( ( ( G e. USGraph /\ X e. V ) /\ ( ( # ` U ) = N /\ A. x e. U A. y e. U { x , y } e/ E ) ) /\ ( f : C -1-1-onto-> W /\ ( f ` X ) = 0 ) ) -> f : ( Vtx ` ( G ISubGr C ) ) -1-1-onto-> W )
25 fvexd 
 |-  ( ( ( ( G e. USGraph /\ X e. V ) /\ ( ( # ` U ) = N /\ A. x e. U A. y e. U { x , y } e/ E ) ) /\ ( f : C -1-1-onto-> W /\ ( f ` X ) = 0 ) ) -> ( Edg ` ( G ISubGr C ) ) e. _V )
26 25 mptexd 
 |-  ( ( ( ( G e. USGraph /\ X e. V ) /\ ( ( # ` U ) = N /\ A. x e. U A. y e. U { x , y } e/ E ) ) /\ ( f : C -1-1-onto-> W /\ ( f ` X ) = 0 ) ) -> ( i e. ( Edg ` ( G ISubGr C ) ) |-> ( f " i ) ) e. _V )
27 eqid 
 |-  ( Edg ` ( G ISubGr C ) ) = ( Edg ` ( G ISubGr C ) )
28 eqid 
 |-  ( i e. ( Edg ` ( G ISubGr C ) ) |-> ( f " i ) ) = ( i e. ( Edg ` ( G ISubGr C ) ) |-> ( f " i ) )
29 1 2 3 4 5 6 7 27 28 isubgr3stgrlem9 
 |-  ( ( ( ( G e. USGraph /\ X e. V ) /\ ( ( # ` U ) = N /\ A. x e. U A. y e. U { x , y } e/ E ) ) /\ ( f : C -1-1-onto-> W /\ ( f ` X ) = 0 ) ) -> ( ( i e. ( Edg ` ( G ISubGr C ) ) |-> ( f " i ) ) : ( Edg ` ( G ISubGr C ) ) -1-1-onto-> ( Edg ` ( StarGr ` N ) ) /\ A. e e. ( Edg ` ( G ISubGr C ) ) ( f " e ) = ( ( i e. ( Edg ` ( G ISubGr C ) ) |-> ( f " i ) ) ` e ) ) )
30 f1oeq1 
 |-  ( g = ( i e. ( Edg ` ( G ISubGr C ) ) |-> ( f " i ) ) -> ( g : ( Edg ` ( G ISubGr C ) ) -1-1-onto-> ( Edg ` ( StarGr ` N ) ) <-> ( i e. ( Edg ` ( G ISubGr C ) ) |-> ( f " i ) ) : ( Edg ` ( G ISubGr C ) ) -1-1-onto-> ( Edg ` ( StarGr ` N ) ) ) )
31 fveq1 
 |-  ( g = ( i e. ( Edg ` ( G ISubGr C ) ) |-> ( f " i ) ) -> ( g ` e ) = ( ( i e. ( Edg ` ( G ISubGr C ) ) |-> ( f " i ) ) ` e ) )
32 31 eqeq2d 
 |-  ( g = ( i e. ( Edg ` ( G ISubGr C ) ) |-> ( f " i ) ) -> ( ( f " e ) = ( g ` e ) <-> ( f " e ) = ( ( i e. ( Edg ` ( G ISubGr C ) ) |-> ( f " i ) ) ` e ) ) )
33 32 ralbidv 
 |-  ( g = ( i e. ( Edg ` ( G ISubGr C ) ) |-> ( f " i ) ) -> ( A. e e. ( Edg ` ( G ISubGr C ) ) ( f " e ) = ( g ` e ) <-> A. e e. ( Edg ` ( G ISubGr C ) ) ( f " e ) = ( ( i e. ( Edg ` ( G ISubGr C ) ) |-> ( f " i ) ) ` e ) ) )
34 30 33 anbi12d 
 |-  ( g = ( i e. ( Edg ` ( G ISubGr C ) ) |-> ( f " i ) ) -> ( ( g : ( Edg ` ( G ISubGr C ) ) -1-1-onto-> ( Edg ` ( StarGr ` N ) ) /\ A. e e. ( Edg ` ( G ISubGr C ) ) ( f " e ) = ( g ` e ) ) <-> ( ( i e. ( Edg ` ( G ISubGr C ) ) |-> ( f " i ) ) : ( Edg ` ( G ISubGr C ) ) -1-1-onto-> ( Edg ` ( StarGr ` N ) ) /\ A. e e. ( Edg ` ( G ISubGr C ) ) ( f " e ) = ( ( i e. ( Edg ` ( G ISubGr C ) ) |-> ( f " i ) ) ` e ) ) ) )
35 26 29 34 spcedv 
 |-  ( ( ( ( G e. USGraph /\ X e. V ) /\ ( ( # ` U ) = N /\ A. x e. U A. y e. U { x , y } e/ E ) ) /\ ( f : C -1-1-onto-> W /\ ( f ` X ) = 0 ) ) -> E. g ( g : ( Edg ` ( G ISubGr C ) ) -1-1-onto-> ( Edg ` ( StarGr ` N ) ) /\ A. e e. ( Edg ` ( G ISubGr C ) ) ( f " e ) = ( g ` e ) ) )
36 24 35 jca 
 |-  ( ( ( ( G e. USGraph /\ X e. V ) /\ ( ( # ` U ) = N /\ A. x e. U A. y e. U { x , y } e/ E ) ) /\ ( f : C -1-1-onto-> W /\ ( f ` X ) = 0 ) ) -> ( f : ( Vtx ` ( G ISubGr C ) ) -1-1-onto-> W /\ E. g ( g : ( Edg ` ( G ISubGr C ) ) -1-1-onto-> ( Edg ` ( StarGr ` N ) ) /\ A. e e. ( Edg ` ( G ISubGr C ) ) ( f " e ) = ( g ` e ) ) ) )
37 36 ex 
 |-  ( ( ( G e. USGraph /\ X e. V ) /\ ( ( # ` U ) = N /\ A. x e. U A. y e. U { x , y } e/ E ) ) -> ( ( f : C -1-1-onto-> W /\ ( f ` X ) = 0 ) -> ( f : ( Vtx ` ( G ISubGr C ) ) -1-1-onto-> W /\ E. g ( g : ( Edg ` ( G ISubGr C ) ) -1-1-onto-> ( Edg ` ( StarGr ` N ) ) /\ A. e e. ( Edg ` ( G ISubGr C ) ) ( f " e ) = ( g ` e ) ) ) ) )
38 37 eximdv 
 |-  ( ( ( G e. USGraph /\ X e. V ) /\ ( ( # ` U ) = N /\ A. x e. U A. y e. U { x , y } e/ E ) ) -> ( E. f ( f : C -1-1-onto-> W /\ ( f ` X ) = 0 ) -> E. f ( f : ( Vtx ` ( G ISubGr C ) ) -1-1-onto-> W /\ E. g ( g : ( Edg ` ( G ISubGr C ) ) -1-1-onto-> ( Edg ` ( StarGr ` N ) ) /\ A. e e. ( Edg ` ( G ISubGr C ) ) ( f " e ) = ( g ` e ) ) ) ) )
39 12 38 mpd 
 |-  ( ( ( G e. USGraph /\ X e. V ) /\ ( ( # ` U ) = N /\ A. x e. U A. y e. U { x , y } e/ E ) ) -> E. f ( f : ( Vtx ` ( G ISubGr C ) ) -1-1-onto-> W /\ E. g ( g : ( Edg ` ( G ISubGr C ) ) -1-1-onto-> ( Edg ` ( StarGr ` N ) ) /\ A. e e. ( Edg ` ( G ISubGr C ) ) ( f " e ) = ( g ` e ) ) ) )
40 1 isubgrusgr 
 |-  ( ( G e. USGraph /\ C C_ V ) -> ( G ISubGr C ) e. USGraph )
41 16 40 syl 
 |-  ( ( G e. USGraph /\ X e. V ) -> ( G ISubGr C ) e. USGraph )
42 usgruspgr 
 |-  ( ( G ISubGr C ) e. USGraph -> ( G ISubGr C ) e. USPGraph )
43 uspgrushgr 
 |-  ( ( G ISubGr C ) e. USPGraph -> ( G ISubGr C ) e. USHGraph )
44 41 42 43 3syl 
 |-  ( ( G e. USGraph /\ X e. V ) -> ( G ISubGr C ) e. USHGraph )
45 stgrusgra 
 |-  ( N e. NN0 -> ( StarGr ` N ) e. USGraph )
46 usgruspgr 
 |-  ( ( StarGr ` N ) e. USGraph -> ( StarGr ` N ) e. USPGraph )
47 uspgrushgr 
 |-  ( ( StarGr ` N ) e. USPGraph -> ( StarGr ` N ) e. USHGraph )
48 45 46 47 3syl 
 |-  ( N e. NN0 -> ( StarGr ` N ) e. USHGraph )
49 4 48 ax-mp 
 |-  ( StarGr ` N ) e. USHGraph
50 eqid 
 |-  ( Vtx ` ( G ISubGr C ) ) = ( Vtx ` ( G ISubGr C ) )
51 5 fveq2i 
 |-  ( Vtx ` S ) = ( Vtx ` ( StarGr ` N ) )
52 6 51 eqtri 
 |-  W = ( Vtx ` ( StarGr ` N ) )
53 eqid 
 |-  ( Edg ` ( StarGr ` N ) ) = ( Edg ` ( StarGr ` N ) )
54 50 52 27 53 gricushgr 
 |-  ( ( ( G ISubGr C ) e. USHGraph /\ ( StarGr ` N ) e. USHGraph ) -> ( ( G ISubGr C ) ~=gr ( StarGr ` N ) <-> E. f ( f : ( Vtx ` ( G ISubGr C ) ) -1-1-onto-> W /\ E. g ( g : ( Edg ` ( G ISubGr C ) ) -1-1-onto-> ( Edg ` ( StarGr ` N ) ) /\ A. e e. ( Edg ` ( G ISubGr C ) ) ( f " e ) = ( g ` e ) ) ) ) )
55 44 49 54 sylancl 
 |-  ( ( G e. USGraph /\ X e. V ) -> ( ( G ISubGr C ) ~=gr ( StarGr ` N ) <-> E. f ( f : ( Vtx ` ( G ISubGr C ) ) -1-1-onto-> W /\ E. g ( g : ( Edg ` ( G ISubGr C ) ) -1-1-onto-> ( Edg ` ( StarGr ` N ) ) /\ A. e e. ( Edg ` ( G ISubGr C ) ) ( f " e ) = ( g ` e ) ) ) ) )
56 55 adantr 
 |-  ( ( ( G e. USGraph /\ X e. V ) /\ ( ( # ` U ) = N /\ A. x e. U A. y e. U { x , y } e/ E ) ) -> ( ( G ISubGr C ) ~=gr ( StarGr ` N ) <-> E. f ( f : ( Vtx ` ( G ISubGr C ) ) -1-1-onto-> W /\ E. g ( g : ( Edg ` ( G ISubGr C ) ) -1-1-onto-> ( Edg ` ( StarGr ` N ) ) /\ A. e e. ( Edg ` ( G ISubGr C ) ) ( f " e ) = ( g ` e ) ) ) ) )
57 39 56 mpbird 
 |-  ( ( ( G e. USGraph /\ X e. V ) /\ ( ( # ` U ) = N /\ A. x e. U A. y e. U { x , y } e/ E ) ) -> ( G ISubGr C ) ~=gr ( StarGr ` N ) )
58 57 ex 
 |-  ( ( G e. USGraph /\ X e. V ) -> ( ( ( # ` U ) = N /\ A. x e. U A. y e. U { x , y } e/ E ) -> ( G ISubGr C ) ~=gr ( StarGr ` N ) ) )