0
A simple graph with n vertices and k components can have atmost how many edges?
Wiki User
∙ 15y ago
In a connected component of a graph with Mi vertices, the maximum number of edges is
MiC2 or Mi(Mi-1)/2. So if we have k components and each component has Mi vertices
then the maximum number of edges for the graph is M1C2+M2C2+...+MKC2.
Of course the sum of Mi as i goes from 1 to k must be n since the sum of the vertices in each component is the sum of all the vertices in the graph which you gave as n.
Where MC2 means choose 2 from M and there are M(M-1)/2 ways to do that.
Wiki User
∙ 15y ago
Add your answer:
Earn +20 pts
What is the maximum number of distinct edges in an undirected graph with N vertices?
Let G be a complete graph with n vertices. Consider the case where n=2. With only 2 vertices it is clear that there will only be one edge. Now add one more vertex to get n = 3. We must now add edges between the two old vertices and the new one for a total of 3 vertices. We see that adding a vertex to a graph with n vertices gives us n more edges. We get the following sequence Edges on a graph with n vertices: 0+1+2+3+4+5+...+n-1. Adding this to itself and dividing by two yields the following formula for the number of edges on a complete graph with n vertices: n(n-1)/2.
Show that the star graph is the only bipartiate graph which is a tree?
A star graph, call it S_k is a complete bipartite graph with one vertex in the center and k vertices around the leaves. To be a tree a graph on n vertices must be connected and have n-1 edges. We could also say it is connected and has no cycles. Now a star graph, say S_4 has 3 edges and 4 vertices and is clearly connected. It is a tree. This would be true for any S_k since they all have k vertices and k-1 edges. And Now think of K_1,k as a complete bipartite graph. We have one internal vertex and k vertices around the leaves. This gives us k+1 vertices and k edges total so it is a tree. So one way is clear. Now we would need to show that any bipartite graph other than S_1,k cannot be a tree. If we look at K_2,k which is a bipartite graph with 2 vertices on one side and k on the other,can this be a tree?
How do you count rectangles in a pattern?
You count the edges
How many cutting edges does a grain of sand have?
57
What is a cult center?
the center of the cult. Not the edges or outside. Not necessarily inside, but rather absolutely central, at the center most point, equally positioned in diameter from the edges of the cult.
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.
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.
Are vertices edges?
No. Edges join vertices; or, put another way, edges meet at vertices.
How many edges corners faces does a Heptahedron?
A heptahedron has 7 faces. It can have 6 vertices and 11 edges, or7 vertices and 12 edges, or8 vertices and 13 edges, or9 vertices and 14 edges, or10 vertices and 15 edges.
What has no edges or vertices?
A point would have neither edges or vertices
What is the difference between edges and vertices in Math?
Edges are the lines that connect the vertices. The vertices are the actual points where the edges meet.
Difference between vertices and edges?
Vertices are points (corners) and edges are lines that connect vertices
In depth first traversal of a graph G with n vertices k edges are marked as tree edges the no of connected components in G is?
n-k-1
How many edges and vertices does a cube have?
12 edges, 8 vertices
How many vertices And edges does a trianglerpriamid?
# of vertices: 6 # of edges: 5
How many vertices and edges triangular HAS get it right?
A triangle has 3 edges and 3 vertices. A triangular prism has 9 edges and 6 vertices.
How many edges and vertices's does a square pyramid have?
heck if I know * * * * * 8 edges and 5 vertices (not vertices's).
