I'm trying to prove the following: consider the de Bruijn graph $$ G(2,n) $$ I'm trying to prove that for $$ n \geq 4 $$ if I remove the vertices $$ v_1 = 00..0, v_2 = 11..1 $$ and all the edges that touch them, the new graph that is left is still connected.
can someone please help me out with a formal proof? I understand why it's true, because I remove the vertices "from the side" which does not touch any inner vertices (and this inner group of vertices is connected).
I tried to show it by creating new abc where each of the vertices that is left after the elimination of $$ v_1,v_2 $$ together with the adequate edges in the old graph will be copied to a new one in accordance to it's place in the abc. basically I'm trying to "shift" the abc backwards and create new de Bruijn graph $$ G(2,n-2) $$ but I'm not sure if it's correct or how to write that formally.
Thank you very much for your help!
I don't 100% understand your plan, but I suspect you're overthinking it.
Let's let $G'$ be the graph $G(2,n)$ with the two vertices removed. Let $u,v$ be two arbitrary vertices in $G'$. Note that $u$ and $v$ are two binary strings of the length $n$ by the construction of the De Bruijn graph.
Also keep in mind that there is a natural correspondence between a $(u,v)$-path in $G(2,n)$ and a binary string whose first $n$ characters are $u$ and whose last $n$ characters are $v$. So all we need to do to show that $G'$ is strongly diconnected is to show that there is a binary string that starts with $u$, ends with $v$, and does not contain $n$ or more consecutive common bits.
To that end, let $x$ be the binary string of shortest length whose first $n$ characters are $u$ and whose last $n$ characters are $v$. ($uv$ itself is such a string, so there must be a shortest one by the well-ordering of the natural numbers.) Could $x$ contain $n$ consecutive digits? No. The digits could not be at the beginning or end of the string, since $u$ and $v$ were vertices in $G'$ and $000...0$ and $111...1$ were removed. And if the consecutive digits were in the middle, you could remove one of the extra digits and have a shorter string satisfying the conditions, contrary to the choice of $x$ as the shortest such string. Therefore, $x$ corresponds to a $(u,v)$-path that exists completely in $G'$. Since $u$ and $v$ were arbitrary vertices, $G'$ is strongly diconnected.