| Line 17: | Line 17: | ||
Wikipedia has a pretty good page about hypercube bipartiteness: http://en.wikipedia.org/wiki/Hypercube_graph | Wikipedia has a pretty good page about hypercube bipartiteness: http://en.wikipedia.org/wiki/Hypercube_graph | ||
| − | The basic idea is that any <math>Q_{n+1}</math> graph can be made by combining 2 <math>Q_n</math> graphs and joining the corresponding vertices together with an edge. | + | The basic idea is that any <math>Q_{n+1}</math> graph can be made inductively by combining 2 <math>Q_n</math> graphs and joining the corresponding vertices together with an edge. |
[[Image:hypercubeconstruction_MA375Fall2008walther.png|thumb|right|Inductive construction of Q<sub>3</sub> using two Q<sub>2</sub> hypercubes.|300px]] | [[Image:hypercubeconstruction_MA375Fall2008walther.png|thumb|right|Inductive construction of Q<sub>3</sub> using two Q<sub>2</sub> hypercubes.|300px]] | ||
Revision as of 08:05, 7 November 2008
So this question asks for which valus of n are Kn, Cn, Wn and Qn bipartite.
>>> are we supposed to consider n=0 or are these graphs only defined for n>0?--Tsnowdon 18:18, 1 November 2008 (UTC)
--- n>0, otherwise the graph would have no vertices. rtabchou
Are we supposed to consider n=1 for K1 as bipartite, or do we need at least 2 vertices for a bipartite graph?
I think it's supposed to be n > 1.
You should consider K1 as bipartite, it is perfectly legal to have one of the sets V1 or V2 to be empty. The definition requires V1 and V2 to be disjoint, but doesn't require them both to be nonempty.
--Asuleime 22:55, 5 November 2008 (UTC)
Can anyone explain the bipartiteness of hypercubes? I can tell $ Q_1 $, $ Q_2 $ and $ Q_3 $ are bipartite but couldn't figure out how to show that $ Q_n $ is.--Mkorb 10:56, 7 November 2008 (UTC)
Wikipedia has a pretty good page about hypercube bipartiteness: http://en.wikipedia.org/wiki/Hypercube_graph
The basic idea is that any $ Q_{n+1} $ graph can be made inductively by combining 2 $ Q_n $ graphs and joining the corresponding vertices together with an edge.
Hopefully this picture helps.
--Jniederh 12:35, 7 November 2008 (UTC)
