Let $G_{2,n}$ be a de-bruijn graph.
We remove the vertex 11...11 and the vertex 00...00 and all edges connected to them.
Q: For which range of values for n the new graph has Eulerian cycle?
We know that in order for a graph to have an Eulerian cycle we must prove that $d_{in}=d_{out}$
for each vertex.
I proved that for the vertex that didn't get affected by this change $d_{in}=d_{out}=2$
But for the affected ones, that's not related to n and always $d_{in}$ isn't equal to $d_{out}$
For example: for 01…1 $d_{in}=2, d_{out}=1$
and that conradicts that there is n for which this is true.
Her's an image:
Best Answer
Your proof can only have a flaw in it if you have overlooked an edge case for a very small value of $n$. Your proof doesn't apply in the cases $n=1$ and $n=2$. Write it out carefully, and note what assumptions you are making, and where you use $n>2$
When $n=1$, we delete all the vertices. Is the graph with no vertices a graph? Some people say yes, some say no. If your answer is "yes", then is the path with with no vertices a cycle? It vacuously visits all the vertices, so if it's a cycle, it's Eulerian. I get you argue that it's a cycle, if the definition is couched in the form, "if $u$ is the initial vertex, and $v$ is the terminal vertex then $u=v$." Anyway, this case isn't interesting.
In the $n=2$ case, there is an Eulerian cycle. I leave this one to you.