Definition:Vertex Deletion

From ProofWiki
Jump to navigation Jump to search

Definition

Let $G = \struct {V, E}$ be an (undirected) graph.

Let $W \subseteq V$ be a set of vertices of $G$.


Then the graph obtained by deleting $W$ from $G$, denoted by $G - W$, is the subgraph induced by $V \setminus W$.


Alternatively:

$G - W = \struct {V \setminus W, \set {e \in E : e \cap W = \O} }$

Informally, $G - W$ is the graph obtained from $G$ by removing all vertices in $W$ and all edges incident to those vertices.


If $W$ is a singleton such that $W = \set v$, then $G - W$ may be expressed $G - v$.


Also see


Sources