Notation: What does this square brackets notation in graph theory mean?

Question

I'm reading some notes on a first course in graph theory and have came across this line in the proof of Hall's marriage theorem:

...then there is some $A \subset X$ with $|\Gamma(A)| = |A|$. Let $G' = G[A \cup \Gamma(A)]$ and $G'' = G[(X \backslash A) \cup (Y \backslash Γ(A))]$...

here, $G = X \cup Y$ is a bipartite graph with classes $X$ and $Y$. $\Gamma(A)$ is the set of all vertices connected to some vertex in $A$.

What does this square brackets notation, seen in the symbols $G[A \cup \Gamma(A)]$ and $G[(X \backslash A) \cup (Y \backslash Γ(A))]$ mean? I can't seem to spot a definition of it anywhere in the notes.

Answer 1

In this context (and almost always, actually), $G[S]$ denotes the subgraph of $G$ induced by $S$: its vertex set is $S$ and its edge set is the set of all edges of $G$ whose endpoints are both in $S$.

More specifically:

• $G[A \cup \Gamma(A)]$ is the bipartite graph with $A$ on one side and $\Gamma(A)$ on the other, joined by the same edges as went between those sets in $G$.
• $G[(X \setminus A) \cup (Y \setminus \Gamma(A))]$ is the bipartite graph with $X \setminus A$ on one side and $Y \setminus \Gamma(A)$ on the other, joined by the same edges as went between those sets in $G$.

We can also interpret induced subgraphs as the subgraphs we get by deleting certain vertices. For example, $G[(X \setminus A) \cup (Y \setminus \Gamma(A))]$ can be thought of as the graph we get from $G$ by deleting the vertices in $A$ from one side, and the vertices in $\Gamma(A)$ from the other. (We delete an edge whenever one or both of its endpoints are deleted, but keep all other edges.)

This is only another way to say the same thing, but sometimes it is a more convenient way to think about the process.