Question 95
Let $G$ be a finite undirected graph, let $n,d$ be positive integers such that every vertex of $G$ has degree at most $d$, and fix a vertex $x$. Let $a(n,x)$ be the number of connected induced subgraphs of $G$ with $n$ vertices that contain $x$. An induced subgraph $U$ uses vertices of $G$ and, for vertices $x,y$ of $U$, contains the edge joining $x$ and $y$ if and only if that edge belongs to $G$.
1. Prove that $a(n,x)\le2^{nd}$.
2. Prove that $a(n,x)\le\left(\frac{(d+1)^{d+1}}{d^d}\right)^n$.
1. Prove that $a(n,x)\le2^{nd}$.
2. Prove that $a(n,x)\le\left(\frac{(d+1)^{d+1}}{d^d}\right)^n$.