2 votes 2 votes Maximum no of edges in a triangle-free, simple planar graph with 10 vertices Graph Theory graph-theory discrete-mathematics graph-connectivity + – Parshu gate asked Dec 23, 2017 • retagged Oct 9, 2023 by Hira Thakur Parshu gate 825 views answer comment Share Follow See 1 comment See all 1 1 comment reply smsubham commented Jan 26, 2020 reply Follow Share 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 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes 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 Akash Mittal answered Dec 23, 2017 Akash Mittal comment Share Follow See all 2 Comments See all 2 2 Comments reply akash.dinkar12 commented Nov 15, 2018 reply Follow Share for a triangle-free graph, can't have any vertex with degree 1 or 2?? 0 votes 0 votes Sonu12345 commented Jul 24, 2022 reply Follow Share Degree can't 1or 2 because through this can't form planar graph 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes 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$. krish__ answered Dec 24, 2017 krish__ comment Share Follow See all 0 reply Please log in or register to add a comment.