Hypercubes and bipartite graphs not isomorphic to subgraph of k-cube

1.2k Views Asked by At
  1. Is hypercube and k-cube the same?
  2. 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?
1

There are 1 best solutions below

2
On BEST ANSWER

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.