# math

posted by .

Suppose G is a connected, simple, planar graph with 100 vertices. What is the largest possible number of edges in G?

• math -

Euler's formula: e ≤ 3v − 6 if v ≥ 3

Thus, for v=100, e ≤ 294

## Similar Questions

1. ### math

(a). For any connected graph G, all internal nodes of the BFS tree on G have the same number of children. (b). For any connected graph G, the DFS tree on G and the BFS tree on G have the same number of edges.
2. ### math

Suppose G is a connected, simple, planar graph with 100 vertices. What is the largest possible number of edges in G?
3. ### Geaometry (Graph)

A graph G has 200000 edges and for any 3 vertices v,w,x, at least one of the edges vw,wx,xv is not present in G. What is the least number of vertices that G can have?
4. ### Geometry

A simple graph G has 200000 edges and for any 3 vertices v,w,x, at least one of the edges vw,wx,xv is not present in G. What is the least number of vertices that G can have?
5. ### MATHS

A simple graph G has 200000 edges and for any 3 vertices v,w,x, at least one of the edges vw,wx,xv is not present in G. What is the least number of vertices that G can have?
6. ### heelp math

A graph is constructed iteratively according to the following algorithm. The graph starts as a single vertex. With probability p, the graph stops here. Otherwise, 3 new vertices are constructed and joined to this vertex. If we have …
7. ### Discrete Mathematics

Consider the complete graph with 5 vertices, denoted by K5. A. Draw the graph. B. How many edges are in K5?
8. ### Discrete Mathematics

Let G be a graph with vertex set V = {v1, v2, v3, v4, v5}. A. Is it possible for the degrees of the vertices to be 3, 6, 2, 1, 5, respectively?
9. ### Graph Theory/ Algorithms / Computer science

I am working on this problem from the book, Data Structures & Algorithm Analysis in C++. The problem is: 9.40 Give a polynomial-time algorithm that ﬁnds ceil(V /2) vertices that collectively cover at least three-fourths (3/4) …
10. ### math

how many edges , vertices and faces does a cylinder have?

More Similar Questions