|
$B$ is an n-dimensional hypercube, considered as undirected graph. Let $A$ be a subset of the vertices of $B$ such that $|A| \gt 2^{n-1}$. Let $H$ is a subgraph of $B$ induced by $A$. Prove that $H$ has at least $n$ edges. Any help, would be greatly appreciated. |
|||||||||||
|
|
Temporarily consider one of the $n$ coordinate axes. Your hypercube has $2^{n-1}$ edges parallel to that axis. Since $B$ has more than $2^{n-1}$ vertices, it must have two on the same one of those $2^{n-1}$ edges. So $H$ has an edge parallel to the coordinate axis under consideration. Apply this to all $n$ of the axes. |
|||||||
|
|
We can build n-dimensional hypercube using two $(n-1)$-dimensional hypercubes. This gives us the vertices set power $|Vn| = 2^{n}$ for the n-dimensional hypercube Gn(Vn, En). Knowing |Vn-1| and |En-1| for (n-1)-dimensional hypercube we know |En| for n-dimensional hypercube. |En| = 2*|En-1| + $2^{n-1}$. Solving this recurrence relation gives us |En| for any dimension. |En| = $n*2^{n-1}$. Then we choose at least $(2^{n-1}+1)$ vertices to be in the $A$ subset by choosing at most $(2^{n-1} - 1)$ vertices that wont be in $A$. We know that every vertex in $n$-dimensional hypercube is connected to $n$ edges (or less if we remove some vertices). So removing the maximum of $(2^{n-1} - 1)$ vertices removes no more than $r = (2^{n-1} - 1)*n$ edges. $r = (2^{n-1} - 1)*n = |En| - n$. It appers that the induced graph H has at least |En| - r edges. |En| - r = |En| - (|En| - n) = n. We can conclude that H has at least n edges. Sorry if there is something unclear. English is not my native language. I would be glad if someone improves my post. I've done my best to format it and make it readable but I am new to LaTeX and I preferred not to use it for now. |
||||
|
|
