- Is hypercube and k-cube the same?
- I did see the question in another post here, but I am not able to comment there since I do not have much reputation, and I am not allowed to post a doubt as answer. I was under the impression that adding an edge between 0-vertex (calling(0,0,..0) so for easiness) and 1-vertex (calling(1,1,..1) so for easiness) (or (1,1,...,1,0) vertex if k is even) will give a sub graph which is not isomorphic to any subgraphs of k-cube, and is clearly bipartite: but unfortunately, isn't any bipartite graph isomorphic to Q1(ignoring trivial case of Q0?
2026-03-27 18:14:56.1774635296
Hypercubes and bipartite graphs not isomorphic to subgraph of k-cube
1.2k Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
1) Yes, people use these terms interchangeably. The advantage of $k$-cube is that it makes explicit what the dimension is. On the other hand, the term hypercube sounds way cooler.
2) No! Two graphs $G$ and $H$ are isomorphic if there is a bijective function from the vertices of $G$ to the vertices of $H$ with the property that two vertices are joined by an edge in $G$ if and only if the image of those two vertices is joined by an edge in $H$.
So if $G$ is isomorphic to $H$, then they must have the same number of vertices, as otherwise the function required in the definition wouldn't be a bijection.
You are claiming that any bipartite graph is isomorphic to $Q_1$ which has only two vertices. On the other hand, I'm sure you can think of some bipartite graphs with more than two vertices, thereby contradicting your claim.