0

What is the maximal number of edges in a graph with n nodes and at least 2 connected components?

For example, in a graph with 7 nodes, how many edges would ensure it is a connected graph?

Gulzar
  • 190
  • Have you tried anything yet - thought any thoughts about the problem? – Mark Bennet Jun 21 '20 at 12:39
  • I thought about counting the max nodes in each connected component, and selecting by the maximum number of total nodes, which would probably arise by a single node being disconnected, meaning a total of (n-1)C2 edges. I can't prove it is the maximum though – Gulzar Jun 21 '20 at 12:49
  • 1
    @Gulzar: See my answer to:$;$ https://math.stackexchange.com/questions/3721225/ – quasi Jun 21 '20 at 13:04

1 Answers1

0

You can partition the graph into 2 separate graphs, say the 7 point graph into a 3 and a 4 point graph, then find the maximum number of lines in each of the two smaller graphs and add. You also need to check that other partitions eg 5 + 2 and 6 + 1 do not give bigger answers. The biggest answer is the one you want. If you want to guarantee connectedness, add 1.

When you try the 7 point graph you will see which partitioning gives the largest answer. Can you see why this works in general? Hint- how many edges must be removed from the maximal graph to disconnect the two smaller graphs?

Peter
  • 1,701