I know that for an undirected graph with n vertices to be connected it must have n - 1 edges. However, my question is what is the minimum number of edges that it can have for it to always be connected. For example, does a graph with n vertices and n + 2 edges have to be always be connected? If not, what is the number of edges it must have for it to always be connected?
1
votes
This question isn't about the programming aspects of this graph-theoretical fact, and so isn't a good fit for Stack Overflow.
– DSM
Interesting homework question, but where is your effort in trying to solve it?
– Ulrich Eckhardt
This question is answered with nicer formatting here: cs.stackexchange.com/questions/7373/…
– user755921
2 Answers
0
votes
If you allow for repeated connections then there is no maximum number. (For example you have 3 vertices a,b,c and the edge (a,b) appears infinity many times but there is no edge that connects with c). So to make this interesting lets say you can't have repeated connections.
For your case of n+2 edges consider if you had a graph with 10 vertices and its edges form two disjoint copies of k5. k5 has 10 edges so we have a a graph with 10 vertices and 20 edges which works as a counter example to your claim. However if you notice in my example if we don't disconnect any edges you cannot add one without connecting the graph.
Another example we can consider (again with 10 vertices) is k9 and a single vertex. k9 has 36 edges (more than my previous example) and the single vertex makes the graph disjoint. In general your maximal example will be k(n-1) and a single vertex.
km has m(m-1)/2 edges so the maximum number of edges you can have and still have a disjoint graph is (n-1)(n-2)/2. Meaning the minimal number of edges to guarantee a n vertex graph (with no self loops or multiple connections) is (n-1)(n-2)/2 + 1.
-1
votes
the maximum number of edges that a n vertices graph can have to not be connected is n-2.
for a graph having 3 vertices you need atleast 2 edges to make it connected which is n-1 so one edge lesser than that will give you the maximum edges with which graph will be disconnected.
does a graph with n vertices and n + 2 edges have to be always be connected : depends whether self loops are allowed or not for example consider a case of 3 vertices and 5 edges so it will be connected by 2 edges and 3 self loops but fir the case of 4 vertices and 6 edges it's possible also and not possible too.
