Eliminación de vértices y aristas en un grafo

La eliminación de un vértice $v$ en un Grafo $G=(V,E)$, resulta en un nuevo grafo $G^{\prime }=(V^{\prime },E^{\prime })$, denotado por $G\setminus v$, tal que

• $V^{\prime }=V\setminus \{v\}$,
• $E^{\prime }=\{e\in E:v\notin e\}$.

Para un subconjunto de vertices $U\subset V$, la eliminación de $U$ del grafo $G$ corresponde con eliminar cada vértice $u\in U$. I.e. resulta en un nuevo grafo $G^{\prime }=(V^{\prime },E^{\prime })$, denotado como $G\setminus U$, donde:

• $V^{\prime }=V\setminus U$,
• $E^{\prime }=\{e\in E:e\cap U=\varnothing \}$.

Adicionalmente, en un ligero abuso de notación, dado un subconjunto de aristas $F\subset E$, denotamos por $G\setminus F$ el grafo resultante de eliminar las aristas en $F$ de $G$. Así, el grafo resultante $G^{\prime }=(V^{\prime },E^{\prime })$ se define por:

• $V^{\prime }=V$,
• $E^{\prime }=E\setminus F$.