Check if the graph is bi-partite [closed]
$begingroup$
Let $G$ be the graph whose vertex set is the set of $k$-tuples with coordinates in ${0, 1}$, with $x$
adjacent to $y$ when $x$ and $y$ differ in exactly one position. Determine whether $G$ is bipartite.
I tried it by taking $0$'s at some positions and comparing with others, but was unsuccessful in doing so. Help
graph-theory
edited Dec 15 '18 at 15:55
amWhy
1
$endgroup$
closed as off-topic by amWhy, Brahadeesh, Batominovski, José Carlos Santos, Did Dec 16 '18 at 12:37
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – amWhy, Brahadeesh, Batominovski, José Carlos Santos, Did
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
Let $G$ be the graph whose vertex set is the set of $k$-tuples with coordinates in ${0, 1}$, with $x$
adjacent to $y$ when $x$ and $y$ differ in exactly one position. Determine whether $G$ is bipartite.
I tried it by taking $0$'s at some positions and comparing with others, but was unsuccessful in doing so. Help
graph-theory
edited Dec 15 '18 at 15:55
amWhy
1
$endgroup$
closed as off-topic by amWhy, Brahadeesh, Batominovski, José Carlos Santos, Did Dec 16 '18 at 12:37
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – amWhy, Brahadeesh, Batominovski, José Carlos Santos, Did
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
Let $G$ be the graph whose vertex set is the set of $k$-tuples with coordinates in ${0, 1}$, with $x$
adjacent to $y$ when $x$ and $y$ differ in exactly one position. Determine whether $G$ is bipartite.
I tried it by taking $0$'s at some positions and comparing with others, but was unsuccessful in doing so. Help
graph-theory
edited Dec 15 '18 at 15:55
amWhy
1
$endgroup$
Let $G$ be the graph whose vertex set is the set of $k$-tuples with coordinates in ${0, 1}$, with $x$
adjacent to $y$ when $x$ and $y$ differ in exactly one position. Determine whether $G$ is bipartite.
I tried it by taking $0$'s at some positions and comparing with others, but was unsuccessful in doing so. Help
graph-theory
graph-theory
edited Dec 15 '18 at 15:55
amWhy
1
edited Dec 15 '18 at 15:55
amWhy
1
edited Dec 15 '18 at 15:55
amWhy
1
edited Dec 15 '18 at 15:55
amWhy
1
edited Dec 15 '18 at 15:55
amWhy
1
1
asked Dec 15 '18 at 14:25
user626673
closed as off-topic by amWhy, Brahadeesh, Batominovski, José Carlos Santos, Did Dec 16 '18 at 12:37
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – amWhy, Brahadeesh, Batominovski, José Carlos Santos, Did
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by amWhy, Brahadeesh, Batominovski, José Carlos Santos, Did Dec 16 '18 at 12:37
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – amWhy, Brahadeesh, Batominovski, José Carlos Santos, Did
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Yes it is bi-partite.
Let the 2 sets be $A$ & $B$. I'll put any $x$ in $A$ if the number of zeros in it is even, and in $B$ if odd. Take any $x,y$ in $A$. Either they have the same number of zeros, or differ by at least 2. If they have the same number of zeros, they must differ in at least 2 positions, otherwise they would be the same (or not have the same no. of zeros)! $implies x&y$ are not adjacent. If they differ in at least 2 zeros, again they can't be adjacent. Now take any $m$ in $A$ and any $n$ in $B$. Consider the case when no. of zeroes in $m$ is one less/more than that in $n$. There is a possibility, that the difference is just at one position. Hence, $m&n$ can be adjacent only if they are in different sets.
Hence, the graph is bi-partite!
answered Dec 15 '18 at 14:33
Ankit KumarAnkit Kumar
1,389219
$endgroup$
1
$begingroup$
Thank you, it helped
$endgroup$
– user626673
Dec 15 '18 at 14:41
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Yes it is bi-partite.
Let the 2 sets be $A$ & $B$. I'll put any $x$ in $A$ if the number of zeros in it is even, and in $B$ if odd. Take any $x,y$ in $A$. Either they have the same number of zeros, or differ by at least 2. If they have the same number of zeros, they must differ in at least 2 positions, otherwise they would be the same (or not have the same no. of zeros)! $implies x&y$ are not adjacent. If they differ in at least 2 zeros, again they can't be adjacent. Now take any $m$ in $A$ and any $n$ in $B$. Consider the case when no. of zeroes in $m$ is one less/more than that in $n$. There is a possibility, that the difference is just at one position. Hence, $m&n$ can be adjacent only if they are in different sets.
Hence, the graph is bi-partite!
answered Dec 15 '18 at 14:33
Ankit KumarAnkit Kumar
1,389219
$endgroup$
1
$begingroup$
Thank you, it helped
$endgroup$
– user626673
Dec 15 '18 at 14:41
add a comment |
$begingroup$
Yes it is bi-partite.
Let the 2 sets be $A$ & $B$. I'll put any $x$ in $A$ if the number of zeros in it is even, and in $B$ if odd. Take any $x,y$ in $A$. Either they have the same number of zeros, or differ by at least 2. If they have the same number of zeros, they must differ in at least 2 positions, otherwise they would be the same (or not have the same no. of zeros)! $implies x&y$ are not adjacent. If they differ in at least 2 zeros, again they can't be adjacent. Now take any $m$ in $A$ and any $n$ in $B$. Consider the case when no. of zeroes in $m$ is one less/more than that in $n$. There is a possibility, that the difference is just at one position. Hence, $m&n$ can be adjacent only if they are in different sets.
Hence, the graph is bi-partite!
answered Dec 15 '18 at 14:33
Ankit KumarAnkit Kumar
1,389219
$endgroup$
1
$begingroup$
Thank you, it helped
$endgroup$
– user626673
Dec 15 '18 at 14:41
add a comment |
$begingroup$
Yes it is bi-partite.
Let the 2 sets be $A$ & $B$. I'll put any $x$ in $A$ if the number of zeros in it is even, and in $B$ if odd. Take any $x,y$ in $A$. Either they have the same number of zeros, or differ by at least 2. If they have the same number of zeros, they must differ in at least 2 positions, otherwise they would be the same (or not have the same no. of zeros)! $implies x&y$ are not adjacent. If they differ in at least 2 zeros, again they can't be adjacent. Now take any $m$ in $A$ and any $n$ in $B$. Consider the case when no. of zeroes in $m$ is one less/more than that in $n$. There is a possibility, that the difference is just at one position. Hence, $m&n$ can be adjacent only if they are in different sets.
Hence, the graph is bi-partite!
answered Dec 15 '18 at 14:33
Ankit KumarAnkit Kumar
1,389219
$endgroup$
Yes it is bi-partite.
Let the 2 sets be $A$ & $B$. I'll put any $x$ in $A$ if the number of zeros in it is even, and in $B$ if odd. Take any $x,y$ in $A$. Either they have the same number of zeros, or differ by at least 2. If they have the same number of zeros, they must differ in at least 2 positions, otherwise they would be the same (or not have the same no. of zeros)! $implies x&y$ are not adjacent. If they differ in at least 2 zeros, again they can't be adjacent. Now take any $m$ in $A$ and any $n$ in $B$. Consider the case when no. of zeroes in $m$ is one less/more than that in $n$. There is a possibility, that the difference is just at one position. Hence, $m&n$ can be adjacent only if they are in different sets.
Hence, the graph is bi-partite!
answered Dec 15 '18 at 14:33
Ankit KumarAnkit Kumar
1,389219
answered Dec 15 '18 at 14:33
Ankit KumarAnkit Kumar
1,389219
answered Dec 15 '18 at 14:33
Ankit KumarAnkit Kumar
1,389219
answered Dec 15 '18 at 14:33
Ankit KumarAnkit Kumar
1,389219
1,389219
1
$begingroup$
Thank you, it helped
$endgroup$
– user626673
Dec 15 '18 at 14:41
add a comment |
1
$begingroup$
Thank you, it helped
$endgroup$
– user626673
Dec 15 '18 at 14:41
1
1
$begingroup$
Thank you, it helped
$endgroup$
– user626673
Dec 15 '18 at 14:41
$begingroup$
Thank you, it helped
$endgroup$
– user626673
Dec 15 '18 at 14:41
add a comment |
