0
How many edges must a simple graph with n vertices have in order to guarantee that it is connected?
Wiki User
∙ 13y ago
The non-connected graph on n vertices with the most edges is a complete graph on n-1 vertices and one isolated vertex. So you must have one more than (n-1)n/2 edges to guarantee connectedness. It is easy to see that the extremal graph must be the union of two disjoint cliques (complete graphs). (Proof:In a non-connected graph with parts that are not cliques, add edges to each part until all are cliques. You will not have changed the number of parts. If there are more than two disjoint cliques, you can join cliques [add all edges between them] until there are only two.) It is straightforward to create a quadratic expression for the number of edges in two disjoint cliques (say k vertices in one clique, n-k in the other). Basic algebra will show that the maximum occurs when k=1 or n-1. (We're not allowing values outside that range.)
Wiki User
∙ 13y ago
Add your answer:
Earn +20 pts
How many corner does a triangular pyramid have?
A triangular pyramid has 4 vertices (each vertex has 3 edges connected to it).
Which shap has 5 vertices 12 edges and 6 faces?
There is no simply connected shape with these properties. Euler's characteristic requires that Faces + Vertices = Edges + 2
What solid figure has 4 faces 9 edges and 6 vertices?
It is not any kind of simply connected solid figure because it does not satisfy the Euler characteristic which requires thatFaces + Vertices = Edges + 2It is not any kind of simply connected solid figure because it does not satisfy the Euler characteristic which requires thatFaces + Vertices = Edges + 2It is not any kind of simply connected solid figure because it does not satisfy the Euler characteristic which requires thatFaces + Vertices = Edges + 2It is not any kind of simply connected solid figure because it does not satisfy the Euler characteristic which requires thatFaces + Vertices = Edges + 2
4 faces 6 edges 6 vertices?
The above numbers do not satisfy the Euler characteristic (Faces + Vertices = Edges + 2) and so it is not a simply connected polyhedron.
If faces plus edges equals vertices plus what number follows?
There is no answer to the question as it appears. Faces + Vertices = Edges + 2 (The Euler characteristic of simply connected polyhedra).
How many faces edges and vertices do connected pyramid have?
A Connected Pyramids have 10 Faces, 12 Vertices, 20 Edges.
What is the formula related vertices and edges?
There is not a specific formula fro vertices and edges. The Euler characteristic links the number of vertices, edges AND faces as follows: E + 2 = V + F for a simply connected polyhedron.
How many corner does a triangular pyramid have?
A triangular pyramid has 4 vertices (each vertex has 3 edges connected to it).
Which shap has 5 vertices 12 edges and 6 faces?
There is no simply connected shape with these properties. Euler's characteristic requires that Faces + Vertices = Edges + 2
What solid figure has 4 faces 9 edges and 6 vertices?
It is not any kind of simply connected solid figure because it does not satisfy the Euler characteristic which requires thatFaces + Vertices = Edges + 2It is not any kind of simply connected solid figure because it does not satisfy the Euler characteristic which requires thatFaces + Vertices = Edges + 2It is not any kind of simply connected solid figure because it does not satisfy the Euler characteristic which requires thatFaces + Vertices = Edges + 2It is not any kind of simply connected solid figure because it does not satisfy the Euler characteristic which requires thatFaces + Vertices = Edges + 2
4 faces 6 edges 6 vertices?
The above numbers do not satisfy the Euler characteristic (Faces + Vertices = Edges + 2) and so it is not a simply connected polyhedron.
If faces plus edges equals vertices plus what number follows?
There is no answer to the question as it appears. Faces + Vertices = Edges + 2 (The Euler characteristic of simply connected polyhedra).
How many vertices and edges does a quadrilateral pyramid have?
5 vertices and 8 edges.5 vertices and 8 edges.5 vertices and 8 edges.5 vertices and 8 edges.
Is faces plus corners equals edges?
No. Faces + Vertices = Edges + 2 (The Euler characteristic of simply connected polyhedra).
How many faces vertices and edges does a hexagon have?
Pretty simple really: Vertices are corners and edges are boundaries so, a hexagon has six of each.
Euler's rule for a polyhedron?
For a simply connected polyhedron,Faces + Vertices = Edges + 2
The minimum number of edges in a connected cyclic graph on n vertices is?
n-1
