![]() ![]() There must be no more than $4$ faces, for the faceshake lemma to hold. Now, we put things together: we are supposed to draw a graph with $6$ vertices and $9$ edges. Since the sum of the degrees of the faces is at least $4F$. Since the shortest cycle in the desired graph has length $4$, every face would have to have at least four edges around it this means we have the relation ![]() ![]() Note that the edges on the boundary of any face form a cycle - that is, if you traverse them, you end up back where you started. (This is also a standard fact, subject to proofs in standard sources, such as those that appear via Google)Īnother property sometimes called the faceshake lemma is that, if you define the degree of a face to be the number of edges bordering the face, then the sum of the degrees of the faces is twice the number of edges, since each edge borders exactly two faces. I won't go into the proof because, while it's straightforward, it's hard to phrase without mathematical jargon - you can try it out, though! Draw any figure according to these rules and this relation will hold. If you let $V$ be the number of vertices and $E$ be the number of edges and $F$ be the number of faces, you have the following relation: You'll note that such a graph determines a set of faces, which are just the regions cut out by the edges - including one face representing "the outside". Such a figure is called a connected planar graph. It is possible to get from any vertex to any other vertex by following some series of edges. No pair of edges connect the same pair of vertices. You draw a set of curves called edges, each of which begins and ends at a vertex and does not intersect itself or any other edge. You draw some set of points called vertices. This fact follows from something called the "Euler characteristic." Basically, suppose you create a figure obeying the following rules: Especially for mathematicians already familiar with some graph theory, this can serve as a very fast way to solve the problem, but I will expand the theory to, as much as possible, be accessible to all. While hexomino's answer gives a very nice proof from geometric principles, there is a somewhat fast way to see this: simply put, this is impossible because there are too many lines to draw. This is a corollary of Kuratowksi's Theorem and is an example of what they call a $K_$ graph. If it is outside this loop, there is not way to connect it to $B_1$ which is within the larger loop formed by $B_3, R_1, B_2, R_2$. If it is within the loop, then there is not way to connect it to $B_2$, which is outside the loop. Then $R_3$ must be within this loop or outside of it. Without loss of generality, suppose it is the former. In this case, either the sequence of circles $B_1, R_1, B_3, R_2$ or $B_2, R_2, B_3, R_1$ forms a loop whose finite interior is disjoint from that of the original. If it is inside the second loop, there is no way to connect it to $B_1$ which is outside the second loop. If it is inside the first loop, there is no way to connect it to $B_2$ which is outside the first loop. The circle $R_3$ must lie inside one of these loops. The interiors of the loops formed by sequences of circles $B_1, R_1, B_3, R_2$ and $B_2, R_2, B_3, R_1$ are disjoint regions whose union is the interior of the original loop. Since the circle $B_3$ and $R_3$ must be connected to each other, they must be both inside the loop or both outside the loop. Then the circles $B_1, R_1, B_2, R_2$ form a closed loop in the plane. Suppose there exists a way to connect all the circles as specified. This is a problem I've thought about quite a bit too and here is my "proof" for why it cannot be doneįor convenience, let us label the black circles $B_1, B_2, B_3$ and the red circles $R_1, R_2, R_3$. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |