Menu
would minimum be (n-1) edges?
I am unsure about maximum
266
The fewest edges a connected graph on n vertices has is n−1. No graph with n−2 edges is connected. Not all graphs with n−1 edges are connected. Not all graphs with n edges are connected.
The number of edges in complete graph with n node, kn is n(n−1)2.
A graph with no loops and no parallel edges is called a simple graph. The maximum number of edges possible in a single graph with 'n' vertices is nC2 where nC2 = n(n – 1)/2. The number of simple graphs possible with 'n' vertices = 2nc2 = 2n(n-1)/2.
(n-k+1)(n-k)/2 It is because maximum number of edges with n vertices is n(n-1)/2.
Yes.. The minimum number of edges for undirected connected graph is (n-1) edges. To see this, since the graph is connected then there must be a unique path from every vertex to every other vertex and removing any edge will make the graph disconnected.
For the maximum number of edges (assuming simple graphs), every vertex is connected to all other vertices which gives arise for n(n-1)/2 edges (use handshaking lemma). Another way: look over K_n (the complete graph with n vertices) which has the maximum number of edges.
127
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
