The Student Room Group

D1 graph question

In terms of 'n' does a connected graph (only that the others I somewhat understand) have a rule for the minimum number of edges it can have?

Thanks :smile:

Posted from TSR Mobile
n-1 edges. If you have n vertices, then for the first 2 vertices you connect you have one edge, and from then on you need at least 1 edge to add in each new vertex; hence a minimum of n-1.
Reply 2
Avatar for Branny101
Branny101
OP
Original post by FireGarden
n-1 edges. If you have n vertices, then for the first 2 vertices you connect you have one edge, and from then on you need at least 1 edge to add in each new vertex; hence a minimum of n-1.


Sorry I meant "maximum", would there be a rule?

Posted from TSR Mobile
No, not really. There's nothing stopping you putting in more edges. There will be a maximum if you wanted it to be a planar, connected graph (i.e., drawing it without any edges crossing), but finding that out isn't very easy. It requires defining 'faces' for graphs, which is beyond A level spec.
Reply 4
Avatar for Branny101
Branny101
OP
Original post by FireGarden
No, not really. There's nothing stopping you putting in more edges. There will be a maximum if you wanted it to be a planar, connected graph (i.e., drawing it without any edges crossing), but finding that out isn't very easy. It requires defining 'faces' for graphs, which is beyond A level spec.


Coooool thanks fire, that makes sense XD

Posted from TSR Mobile
Original post by Branny101
Coooool thanks fire, that makes sense XD

Posted from TSR Mobile


For a simple graph that does not contain loops or multiple edges, there is a maximum number and that is n(n-1)/2. It is the number of edges in a complete graph on n vertices.

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you