Connect a set of nodes with another set of the same size without intersections [duplicate]
up vote
1
down vote
favorite
This question already has an answer here:
3 Utilities | 3 Houses puzzle?
10 answers
I am quite new to graphs (and could use some practice with math in general) and couldn't find a solution with zero intersections to this problem.
Assume you have two sets of 3 nodes (set H and set L) where each node (ex. h1, h2, h3) from one set should connect to every node on the other set (so l1, l2, l3). Is there any way you could arrange the connections so that there are no intersections?
Example of one edge intersection:
one edge intersection
graph-theory
asked Nov 21 at 19:42
svacxpython
82
marked as duplicate by Misha Lavrov, Ethan Bolker, user10354138, Lord Shark the Unknown, user26857 Nov 22 at 9:51
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
up vote
1
down vote
favorite
This question already has an answer here:
3 Utilities | 3 Houses puzzle?
10 answers
I am quite new to graphs (and could use some practice with math in general) and couldn't find a solution with zero intersections to this problem.
Assume you have two sets of 3 nodes (set H and set L) where each node (ex. h1, h2, h3) from one set should connect to every node on the other set (so l1, l2, l3). Is there any way you could arrange the connections so that there are no intersections?
Example of one edge intersection:
one edge intersection
graph-theory
asked Nov 21 at 19:42
svacxpython
82
marked as duplicate by Misha Lavrov, Ethan Bolker, user10354138, Lord Shark the Unknown, user26857 Nov 22 at 9:51
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
1
(I don't mean to imply that you were wrong to ask this question - but this is the three utilities problem, which is very famous in graph theory, so it has been asked before, and there is no sense in reproducing the many good answers there.)
– Misha Lavrov
Nov 21 at 20:32
@MishaLavrov thank you, I didnt know this was a known problem in graph theory
– svacxpython
Nov 22 at 9:52
I think the problem is not solvable! Thank you both for the answers :)
– svacxpython
Nov 22 at 10:04
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
This question already has an answer here:
3 Utilities | 3 Houses puzzle?
10 answers
I am quite new to graphs (and could use some practice with math in general) and couldn't find a solution with zero intersections to this problem.
Assume you have two sets of 3 nodes (set H and set L) where each node (ex. h1, h2, h3) from one set should connect to every node on the other set (so l1, l2, l3). Is there any way you could arrange the connections so that there are no intersections?
Example of one edge intersection:
one edge intersection
graph-theory
asked Nov 21 at 19:42
svacxpython
82
This question already has an answer here:
3 Utilities | 3 Houses puzzle?
10 answers
I am quite new to graphs (and could use some practice with math in general) and couldn't find a solution with zero intersections to this problem.
Assume you have two sets of 3 nodes (set H and set L) where each node (ex. h1, h2, h3) from one set should connect to every node on the other set (so l1, l2, l3). Is there any way you could arrange the connections so that there are no intersections?
Example of one edge intersection:
one edge intersection
This question already has an answer here:
3 Utilities | 3 Houses puzzle?
10 answers
graph-theory
graph-theory
asked Nov 21 at 19:42
svacxpython
82
asked Nov 21 at 19:42
svacxpython
82
asked Nov 21 at 19:42
svacxpython
82
asked Nov 21 at 19:42
svacxpython
82
asked Nov 21 at 19:42
svacxpython
82
82
marked as duplicate by Misha Lavrov, Ethan Bolker, user10354138, Lord Shark the Unknown, user26857 Nov 22 at 9:51
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by Misha Lavrov, Ethan Bolker, user10354138, Lord Shark the Unknown, user26857 Nov 22 at 9:51
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
1
(I don't mean to imply that you were wrong to ask this question - but this is the three utilities problem, which is very famous in graph theory, so it has been asked before, and there is no sense in reproducing the many good answers there.)
– Misha Lavrov
Nov 21 at 20:32
@MishaLavrov thank you, I didnt know this was a known problem in graph theory
– svacxpython
Nov 22 at 9:52
I think the problem is not solvable! Thank you both for the answers :)
– svacxpython
Nov 22 at 10:04
add a comment |
1
(I don't mean to imply that you were wrong to ask this question - but this is the three utilities problem, which is very famous in graph theory, so it has been asked before, and there is no sense in reproducing the many good answers there.)
– Misha Lavrov
Nov 21 at 20:32
@MishaLavrov thank you, I didnt know this was a known problem in graph theory
– svacxpython
Nov 22 at 9:52
I think the problem is not solvable! Thank you both for the answers :)
– svacxpython
Nov 22 at 10:04
1
1
(I don't mean to imply that you were wrong to ask this question - but this is the three utilities problem, which is very famous in graph theory, so it has been asked before, and there is no sense in reproducing the many good answers there.)
– Misha Lavrov
Nov 21 at 20:32
(I don't mean to imply that you were wrong to ask this question - but this is the three utilities problem, which is very famous in graph theory, so it has been asked before, and there is no sense in reproducing the many good answers there.)
– Misha Lavrov
Nov 21 at 20:32
@MishaLavrov thank you, I didnt know this was a known problem in graph theory
– svacxpython
Nov 22 at 9:52
@MishaLavrov thank you, I didnt know this was a known problem in graph theory
– svacxpython
Nov 22 at 9:52
I think the problem is not solvable! Thank you both for the answers :)
– svacxpython
Nov 22 at 10:04
I think the problem is not solvable! Thank you both for the answers :)
– svacxpython
Nov 22 at 10:04
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
accepted
Here is a solution: A graph $G$ is planar then $|E(G)|leq 3|v(G)|-6$. If furthermore it is triangle free, then $|E(G)| leq 2|V(G)|-4$. For $K_{3,3}$, It doesn't contains triangle as it doesn't contain odd cycle. So apply the second formula we get: $9leq 2*6-4=8$ which is not possible! So it cannot be planar.
To show $|E(G)| leq 2|V(G)|-4$, we will use Euler's equation: $|V|-|E|+|F|$=2 for planar graph. Notice that if you count the total number of edges surrounding the faces, you count each edge twice. So $sum_{ain F(G)}{len(a)}=2|E(G)|$. Now since the graph has no triangle, each face is bounded by at least 4 edges. So $4|F(G)|leqsum_{ain F(G)}{len(a)}=2|E(G)|$. Solve for $|F|$ in Euler's equation and substitute into the previous inequality to get the desired inequality. Hope I got it right.
answered Nov 21 at 23:20
mathnoob
1,590321
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
Here is a solution: A graph $G$ is planar then $|E(G)|leq 3|v(G)|-6$. If furthermore it is triangle free, then $|E(G)| leq 2|V(G)|-4$. For $K_{3,3}$, It doesn't contains triangle as it doesn't contain odd cycle. So apply the second formula we get: $9leq 2*6-4=8$ which is not possible! So it cannot be planar.
To show $|E(G)| leq 2|V(G)|-4$, we will use Euler's equation: $|V|-|E|+|F|$=2 for planar graph. Notice that if you count the total number of edges surrounding the faces, you count each edge twice. So $sum_{ain F(G)}{len(a)}=2|E(G)|$. Now since the graph has no triangle, each face is bounded by at least 4 edges. So $4|F(G)|leqsum_{ain F(G)}{len(a)}=2|E(G)|$. Solve for $|F|$ in Euler's equation and substitute into the previous inequality to get the desired inequality. Hope I got it right.
answered Nov 21 at 23:20
mathnoob
1,590321
add a comment |
up vote
0
down vote
accepted
Here is a solution: A graph $G$ is planar then $|E(G)|leq 3|v(G)|-6$. If furthermore it is triangle free, then $|E(G)| leq 2|V(G)|-4$. For $K_{3,3}$, It doesn't contains triangle as it doesn't contain odd cycle. So apply the second formula we get: $9leq 2*6-4=8$ which is not possible! So it cannot be planar.
To show $|E(G)| leq 2|V(G)|-4$, we will use Euler's equation: $|V|-|E|+|F|$=2 for planar graph. Notice that if you count the total number of edges surrounding the faces, you count each edge twice. So $sum_{ain F(G)}{len(a)}=2|E(G)|$. Now since the graph has no triangle, each face is bounded by at least 4 edges. So $4|F(G)|leqsum_{ain F(G)}{len(a)}=2|E(G)|$. Solve for $|F|$ in Euler's equation and substitute into the previous inequality to get the desired inequality. Hope I got it right.
answered Nov 21 at 23:20
mathnoob
1,590321
add a comment |
up vote
0
down vote
accepted
up vote
0
down vote
accepted
Here is a solution: A graph $G$ is planar then $|E(G)|leq 3|v(G)|-6$. If furthermore it is triangle free, then $|E(G)| leq 2|V(G)|-4$. For $K_{3,3}$, It doesn't contains triangle as it doesn't contain odd cycle. So apply the second formula we get: $9leq 2*6-4=8$ which is not possible! So it cannot be planar.
To show $|E(G)| leq 2|V(G)|-4$, we will use Euler's equation: $|V|-|E|+|F|$=2 for planar graph. Notice that if you count the total number of edges surrounding the faces, you count each edge twice. So $sum_{ain F(G)}{len(a)}=2|E(G)|$. Now since the graph has no triangle, each face is bounded by at least 4 edges. So $4|F(G)|leqsum_{ain F(G)}{len(a)}=2|E(G)|$. Solve for $|F|$ in Euler's equation and substitute into the previous inequality to get the desired inequality. Hope I got it right.
answered Nov 21 at 23:20
mathnoob
1,590321
Here is a solution: A graph $G$ is planar then $|E(G)|leq 3|v(G)|-6$. If furthermore it is triangle free, then $|E(G)| leq 2|V(G)|-4$. For $K_{3,3}$, It doesn't contains triangle as it doesn't contain odd cycle. So apply the second formula we get: $9leq 2*6-4=8$ which is not possible! So it cannot be planar.
To show $|E(G)| leq 2|V(G)|-4$, we will use Euler's equation: $|V|-|E|+|F|$=2 for planar graph. Notice that if you count the total number of edges surrounding the faces, you count each edge twice. So $sum_{ain F(G)}{len(a)}=2|E(G)|$. Now since the graph has no triangle, each face is bounded by at least 4 edges. So $4|F(G)|leqsum_{ain F(G)}{len(a)}=2|E(G)|$. Solve for $|F|$ in Euler's equation and substitute into the previous inequality to get the desired inequality. Hope I got it right.
answered Nov 21 at 23:20
mathnoob
1,590321
answered Nov 21 at 23:20
mathnoob
1,590321
answered Nov 21 at 23:20
mathnoob
1,590321
answered Nov 21 at 23:20
mathnoob
1,590321
1,590321
add a comment |
add a comment |
1
(I don't mean to imply that you were wrong to ask this question - but this is the three utilities problem, which is very famous in graph theory, so it has been asked before, and there is no sense in reproducing the many good answers there.)
– Misha Lavrov
Nov 21 at 20:32
@MishaLavrov thank you, I didnt know this was a known problem in graph theory
– svacxpython
Nov 22 at 9:52
I think the problem is not solvable! Thank you both for the answers :)
– svacxpython
Nov 22 at 10:04