Proving tripartite graph is always planar

260 Views Asked by At

Consider the complete tripartite graph $K_{a,b,c}$ on $a+b+c$ vertices. Provide an embedding to show that $K_{1,1,n}$ is always planar (for $n\geq 1$). How many faces will this graph have?

I am really not sure how to approach either part. I think I should use euler's formula for the second part, which gives $v + f - e = 2$. Here, we'd have $v = n + 2$ and so we obtain $e = n + f$. Not so sure if I can get a better value.

I will appreciate your help in solving this problem

1

There are 1 best solutions below

2
On

For the embedding, consider placing one vertex at $(-1,0)$, one at $(1,0)$, and the other $n$ along the positive $y$ axis.

You have the correct $v$, so if you compute $e=1\cdot 1+1\cdot n +1\cdot n$, you can use Euler’s formula to deduce $f$. Or just count $f$ directly from your embedding, remembering to include the unbounded outer face.