Final answer:
To prove that K5 and K3,3 are non-planar using Euler's formula, we substitute the number of vertices and edges into the formula to find the number of faces. For K5, we get 7 faces, which is more than the 5 vertices it has, making it non-planar. For K3,3, we get 5 faces, which is more than the 6 vertices it has, also making it non-planar.
Step-by-step explanation:
Euler's formula states that for any planar graph with v vertices, e edges, and f faces, the relationship v - e + f = 2 holds. In order to prove that K5 and K3,3 are non-planar using Euler's formula, we need to show that they violate this relationship.
For K5:
K5 is the complete graph with 5 vertices, meaning that every vertex is connected to every other vertex. In this case, we have v = 5 and e = 10 (since each vertex is connected to 4 other vertices). Substituting these values into the Euler's formula, we have: 5 - 10 + f = 2. Solving for f, we get f = 7. However, K5 only has 5 vertices, which means it cannot have 7 faces. Therefore, K5 is non-planar.
For K3,3:
K3,3 is the complete bipartite graph with 3 vertices in each partition, meaning that every vertex in one partition is connected to every vertex in the other partition. In this case, we have v = 6 and e = 9 (since each vertex in one partition is connected to all the vertices in the other partition). Substituting these values into the Euler's formula, we have: 6 - 9 + f = 2. Solving for f, we get f = 5. However, K3,3 only has 6 vertices, which means it cannot have 5 faces. Therefore, K3,3 is non-planar.