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

  • Thread starter Thread starter Aryth1
  • Start date Start date
  • Tags Tags
    Graphs
AI Thread Summary
The discussion focuses on proving that the girth of the d-dimensional hypercube graph, denoted as $H_d$, is 4 for dimensions $d \geq 2$. The base case for $d=2$ is established as a square, which has a girth of 4. Participants suggest using induction to extend the proof to $d+1$, asserting that the structure of the hypercube maintains a girth of 4 as dimensions increase. They clarify that cycles of length 3 cannot exist in the hypercube due to the nature of vertex connections, which require differing components. Overall, the consensus is that the girth remains consistently 4 across all applicable dimensions.
Aryth1
Messages
38
Reaction score
0
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!
 
Physics news on Phys.org
Aryth said:
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?
 
I like Serena said:
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.
 
Aryth said:
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.
 
I like Serena said:
What is the girth of a cube?
More importantly, how did you figure it out exactly?

Aryth said:
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".

Aryth said:
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.
 
I like Serena said:
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.

Evgeny.Makarov said:
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!
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...

Similar threads

Back
Top