MHB Girth of $H_d$ Hypercube Graph: Proving $4$ by Induction

[Aryth1]

My problem is to show that, for $d\geq 2$, the girth of the d-dimensional hypercube graph, I'll call it $H_d$, is $4$.

I'm pretty sure I should use induction, since the base case is simply a cycle of length $4$. Then I suppose that the claim is true for some $d\geq 2$. So I need to show that it's also true for $d+1$, but I'm not sure how I'm supposed to go about this. Any help is appreciated!

 

[I like Serena]

My problem is to show that, for $d\geq 2$, the girth of the d-dimensional hypercube graph, I'll call it $H_d$, is $4$.

I'm pretty sure I should use induction, since the base case is simply a cycle of length $4$. Then I suppose that the claim is true for some $d\geq 2$. So I need to show that it's also true for $d+1$, but I'm not sure how I'm supposed to go about this. Any help is appreciated!

What is the girth of a cube?
More importantly, how did you figure it out exactly?

 

[Aryth1]

What is the girth of a cube?
More importantly, how did you figure it out exactly?

I'm guessing that the girth of a cube will be 4 as well, since each face is a square. Beyond 3-dimensions, though, I can't really see what's going on. I know that the square is a subgraph, but not necessarily that it is a smallest cycle.

I'm not sure what you're asking, though. When $d=2$, I get a square, which is only one cycle of length 4. It doesn't matter if I'm wanting the smallest or the largest, the answer is still 4.

 

[I like Serena]

I'm guessing that the girth of a cube will be 4 as well, since each face is a square. Beyond 3-dimensions, though, I can't really see what's going on. I know that the square is a subgraph, but not necessarily that it is a smallest cycle.

I'm not sure what you're asking, though. When $d=2$, I get a square, which is only one cycle of length 4. It doesn't matter if I'm wanting the smallest or the largest, the answer is still 4.

To measure a girth, you would typically use a measuring tape that goes around.
When you do this with a square, you get its circumference.

When you put a cube on top of that square, you would put the measuring tape around it... and measure the circumference of a square, which is still 4.

When you turn that cube into a hypercube, you'd slide the measuring tape up, and again measure the circumference of a square.By induction, if you have a hypercube of dimension $d$ with girth $4$, and you turn it into a hypercube of dimension $d+1$, you'd slide the measuring tape up, and measure the same circumference, which is $4$, which completes the proof by induction.

 

[Evgeny.Makarov]

What is the girth of a cube?
More importantly, how did you figure it out exactly?

I'm not sure what you're asking, though.

The question is, first of all, about the definition of girth. According to Wikipedia, "the girth of a graph is the length of a shortest cycle contained in the graph".

I know that the square is a subgraph, but not necessarily that it is a smallest cycle.

So we agree that $H_d\le4$, but we need to show that $H_d>3$. Vertices of a hypercube can be represented as tuples $(x_1,\dots,x_n)$ where $x_i\in\{0,1\}$, and two vertices are connected iff they differ in one component. Let's denote $\bar{0}=1$ and $\bar{1}=0$. If there is a cycle of length 3, then for some $1\le i,j\le n$ it has the form
\begin{align}
&(x_1,\dots,x_i,\dots,x_j,\dots,x_n)\\
&(x_1,\dots,\bar{x}_i,\dots,x_j,\dots,x_n)\\
&(x_1,\dots,\bar{x}_i,\dots,\bar{x}_j,\dots,x_n)\\
&(x_1,\dots,x_i,\dots,x_j,\dots,x_n).
\end{align}
The indices $i$ and $j$ must be distinct: if we change $x_i$ twice consecutively, then we pass along the same edge. But then there is no way to go from the third vertex back to the initial one because they differ in two different places.

 

[Aryth1]

To measure a girth, you would typically use a measuring tape that goes around.
When you do this with a square, you get its circumference.

When you put a cube on top of that square, you would put the measuring tape around it... and measure the circumference of a square, which is still 4.

When you turn that cube into a hypercube, you'd slide the measuring tape up, and again measure the circumference of a square.By induction, if you have a hypercube of dimension $d$ with girth $4$, and you turn it into a hypercube of dimension $d+1$, you'd slide the measuring tape up, and measure the same circumference, which is $4$, which completes the proof by induction.

This makes some sense... Although I'm not sure what it means to "slide up". I am curious, though. Graph theory proofs are new to me so I'm trying to learn everything I can.

The question is, first of all, about the definition of girth. According to Wikipedia, "the girth of a graph is the length of a shortest cycle contained in the graph".

So we agree that $H_d\le4$, but we need to show that $H_d>3$. Vertices of a hypercube can be represented as tuples $(x_1,\dots,x_n)$ where $x_i\in\{0,1\}$, and two vertices are connected iff they differ in one component. Let's denote $\bar{0}=1$ and $\bar{1}=0$. If there is a cycle of length 3, then for some $1\le i,j\le n$ it has the form
\begin{align}
&(x_1,\dots,x_i,\dots,x_j,\dots,x_n)\\
&(x_1,\dots,\bar{x}_i,\dots,x_j,\dots,x_n)\\
&(x_1,\dots,\bar{x}_i,\dots,\bar{x}_j,\dots,x_n)\\
&(x_1,\dots,x_i,\dots,x_j,\dots,x_n).
\end{align}
The indices $i$ and $j$ must be distinct: if we change $x_i$ twice consecutively, then we pass along the same edge. But then there is no way to go from the third vertex back to the initial one because they differ in two different places.

I was curious as to whether or not I could use contradiction. Showing that a cycle of length three occurring as impossible in arbitrary dimension seemed like a good route, but I wasn't sure exactly how to word it. Thanks for your help!