| (One intermediate revision by one other user not shown) | |||
| 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]] | ||
| Line 23: | Line 23: | ||
--[[User:Jniederh|Jniederh]] 12:35, 7 November 2008 (UTC) | --[[User:Jniederh|Jniederh]] 12:35, 7 November 2008 (UTC) | ||
| + | |||
| + | |||
| + | ---- | ||
| + | |||
| + | |||
| + | The easy way to show it's bipartite is to consider the binary labels of the vertices. The hypercube was constructed by assigning bit string labels, and then connecting vertices which differed in exactly one spot. | ||
| + | |||
| + | Thus, color vertices with an odd number of 1s red, and the ones with even number of 1s (or zero 1s) blue. From how it was constructed, it's clear a vertex with an odd number of 1s must be connected to a vertex with an even number (or zero) of 1s. | ||
| + | |||
| + | So, red vertices will only connect to blue vertices. | ||
| + | |||
| + | --[[User:Norlow|Norlow]] 18:15, 8 November 2008 (UTC) | ||
Latest revision as of 13:15, 8 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)
The easy way to show it's bipartite is to consider the binary labels of the vertices. The hypercube was constructed by assigning bit string labels, and then connecting vertices which differed in exactly one spot.
Thus, color vertices with an odd number of 1s red, and the ones with even number of 1s (or zero 1s) blue. From how it was constructed, it's clear a vertex with an odd number of 1s must be connected to a vertex with an even number (or zero) of 1s.
So, red vertices will only connect to blue vertices.
--Norlow 18:15, 8 November 2008 (UTC)
