(New page: Show that every connected graph with n vertices has at least n-1 edges. I thought of it like this. At minimum, for n connected vertices in a graph, v1 connects to v2, to v3, ... , to v(n...) |
|||
| Line 2: | Line 2: | ||
I thought of it like this. At minimum, for n connected vertices in a graph, v1 connects to v2, to v3, ... , to v(n-1) to vn. This is n-1 edges. Every set of connected vertices can reduce to this and any other edges are unnecessary to be connected. | I thought of it like this. At minimum, for n connected vertices in a graph, v1 connects to v2, to v3, ... , to v(n-1) to vn. This is n-1 edges. Every set of connected vertices can reduce to this and any other edges are unnecessary to be connected. | ||
| + | |||
| + | ---- | ||
| + | |||
| + | I did it more of a building from the ground-up way. Say we have a single vertex. This has no edges, hence true. To make a the minimum amount of edges when adding another vertex, we have to add a single edge to that vertex, and then so on and so forth adding single edges to each new vertex. Therefore the minimum value of edges is: n-1 for all n. We can model this with the the recursion a_n+1 = a_n +1. | ||
Latest revision as of 06:36, 13 November 2008
Show that every connected graph with n vertices has at least n-1 edges.
I thought of it like this. At minimum, for n connected vertices in a graph, v1 connects to v2, to v3, ... , to v(n-1) to vn. This is n-1 edges. Every set of connected vertices can reduce to this and any other edges are unnecessary to be connected.
I did it more of a building from the ground-up way. Say we have a single vertex. This has no edges, hence true. To make a the minimum amount of edges when adding another vertex, we have to add a single edge to that vertex, and then so on and so forth adding single edges to each new vertex. Therefore the minimum value of edges is: n-1 for all n. We can model this with the the recursion a_n+1 = a_n +1.
