Induced subgraphs

induction graph-theory

A subgraph of $G$ is just any subset of $V(G)$ and any subset of $E(G)$ that is itself a graph. For example, the cycle on six vertices is a subgraph of the complete bipartite graph on eight vertices (choose three vertices from each partite set and the appropriate edges to form a cycle).

An induced subgraph is any subset $S$ of $V(G)$ with edge set $$ \{uv \mid u,v \in S \text{ and } uv \in E(G)\}. $$ In words, you choose only the vertex set for your induced subgraph and then an edge will connect two of those vertices in the induced subgraph if and only if it was present in the original graph. For example, if we choose the same six vertices as in the previous example, the induced subgraph must be the complete bipartite graph on six vertices. We have no freedom to leave out any edges as we did with subgraphs. We must take all and only those edges present between the specified vertices.

Related

Integral $\int_{-\infty}^{\infty}\frac{e^{r \arctan(ax)}+e^{-r \arctan(ax)}}{1+x^2}\cos \left( \frac{r}{2}\log(1+a^2x^2)\right)dx$
Radius of convergence and ratio test
Harmonic number
What needs to be true of $f$ for $f_{xy}=f_{yx}$?
Proving that $\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\dots+\frac{1}{\sqrt{100}}<20$
Frattini subgroup is set of nongenerators
Determinant of $4\times4$ Matrix
Is every element in a set also an element of the powerset?
the value of $\lim\limits_{n\rightarrow\infty}n^2\left(\int_0^1\left(1+x^n\right)^\frac{1}{n} \, dx-1\right)$
Show that if $f$ is integrable on $[a,b]$, then $|f|$ is also integrable.
Finding Jordan Basis of a matrix
Spectrum of a ring is irreducible if and only if nilradical is prime (Atiyah-Macdonald, Exercise 1.19)