Let G be a planar graph with order 8 and size 13. Prove that G is not a bipartite graph Need to find a partition of V into two sets such that all 13 edges go from set to set. There are four ways to partition 8 vertices: (1,7), (2,6), (3,5), (4,4). The first two can have at most seven, respectively 12 edges between sets, The last two are candidates. Does either partition (3,5), (4,4) contain a planar bipartite graph?
There is an order 8 size 12 planar bipartite graph. Draw a cube in perspective so that non of the lines cross. Can you add a 13th line that leaves the diagram planar and bipartite? Code: A--------a |\ /| | \ / | | b--B | | | | | | C--c | | / \ | |/ \| d--------D It would be nice if we had a theorem that said if you had a planar bipartite graph with n vertices, that you had a maximum of 2n - 4 edges. In 1750, Euler proved a theorem that in a connected plane graph diagram with n vertices and e edges, the graph cuts the plane into a number of regions r = 2 + e - n. Example: 2 + 12 - 8 = 6 -- the five polygons and the outside. Consider a maximal bipartite planar graph. Clearly it has no triangles. And so the maximum number of lines happens if every region is bounded by 4 vertices, and every edge is the boundary of two regions. Thus 4r double-counts the edges and we have as a limiting condition: 4r <= 2e. Then Euler's formula becomes a limit on bipartite graphs: 4(2 + e - n) <= 2 e 8 + 4 e - 4 n <= 2 e 2 e <= 4 n - 8 e <= 2n - 4 Example: 12 <= 2*8 - 4 But 13 > 2*8 - 4 so it's impossible to be both bipartite and planar.
Yea, we've just done Euler's formula, there are no triangles as you mention because there are two sets, an even number, so any face must have at least four edges. The lecturer appears to want us to show that with either (3,5) or (4,4) you can't get a bipartite graph that doesn't contain K[sub]3,3[/sub].
