Understanding which conditions a graph has a Eulerian Path

55 Views Asked by At

The graph $Q_n$ is a graph with 2n vertices, where each vertex is associated with a string of 1's and 0's of length n, and where two vertices are adjacent if and only if their associated strings differ in exactly one position. Below I will show the illustration for $Q_{1,2,3}$

Here, I want to find which values of n will the graph have an Eulerian path.

I know for a graph to have an Eulerian path it has to satisfy the following conditions:

  1. All vertices in $Q_n$ except possibly two must have an even degree.
  2. The two vertices that are allowed to have odd degrees

So I have tried to reason with these two conditions. Let us look at condition one. From the reasoning behind the graph, you can say that each vertex in $Q_n$ will be connected to n vertices (you change one number in each spot). So I beleive n must be even based on condition 1

For condition two, I beleive that if $Q_n$ has two vertices with an odd degree, they must be connected. I thinking is that if there were two odd vertices that were not adjacent, you couold create two subgraphs, one of the odd dgree vertices in each. Given this were the case, then each sub graph would have an odd number of vertices. But, we know that $Q_n$ has an even number of vertices.

So, these are the two restrictions I have found, though I am not sure

  1. n must be even
  2. Any pair of odd degree vertices must be adjacent.

Are these restrictions? If so, are there any more?

Edit: It has come to my attention that these are also referred to as n-dimensional hypercubes, if that helps finding similar questions.