Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
1 vote
Maximum no of edges in a triangle-free, simple planar graph with 10 vertices
in Graph Theory 279 views
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

2 Answers

1 vote

Minimum degree in any triangle free graph

$\delta =4$

by using Euler's formula

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


=> 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

for a triangle-free graph, can't have any vertex with degree 1 or 2??
0 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$.

Related questions

3 votes
3 answers
2 votes
2 answers
Consider a 'reversed Kruskal' Algorithm for computing a MST. Initialize T to be the set of all edges in the graph. Now consider edges from largest to smallest cost. For each edge, delete it from T if that edge belongs to a cycle in T. Assuming all the edge costs are distinct, does this new algorithm correctly compute a MST? a) Yes b) no c) cant say
asked Sep 14, 2017 in Graph Theory Rakshit Gupta 392 views
2 votes
0 answers
Let G be a planar Graph Such that every phase is bordered by exactly 3 edges which of the following can never be value for X(G) a)2 b)3 C)4 d)none of these
asked Nov 11, 2017 in Graph Theory Parshu gate 380 views
0 votes
0 answers
Let G be a planar graph with 7 vertices, 10 edges and 3 components then the number of regions are : a)24 b)37 c)7 d)10 Answer given : 7 How to solve this ? Is there any formulae for number of regions calculation? The only one I know is r=e-n+2 for any planar graph.
asked Dec 25, 2017 in Graph Theory Sourajit25 220 views