graph theory

Question

Maximum no of edges in a triangle-free, simple planar graph with 10 vertices

Comments

m <= 2n - 4, m is no of edges, n is no of vertices (for triangle free simple connected simple planar graph)

m <= 20-4

m <= 16

Answer 1

Minimum degree in any triangle free graph

$\delta =4$

by using Euler's formula

e-n+(k+1) =r   {k=#f connected components}

e-10+2=r

=> e-8=r

As, min degree of region is 4

$4r\leq 2e$

=> 4(e-8) $\leq$ 2e

=> 4e-32  $\leq$ 2e

=> e $\leq$16

Comments

for a triangle-free graph, can't have any vertex with degree 1 or 2??

---

Degree can't 1or 2 because through this can't form planar graph

Answer 2

For a triangle free graph, every face has degree $\ge$ 4. Therefore $2e \le 4f \implies f \ge \frac{e}{2}$ (This is because $\sum deg(f_i) = 2e $). We know from Euler's formulae that $n-e+f=2$. So, $f=2+e-n \implies \frac{e}{2} \ge 2+e-n \implies 2(n-2) \ge e$. Here $n=10$. Therefore, $e\le 16$.