Linear Algebra and Its Applications · Problem 2.5.20

Vector Spaces — Gilbert Strang

Mathematics · graphs-and-networks

Problem

Why does a complete graph with

n = 6

nodes have

m = 15

edges? A spanning tree connecting all six nodes has \_\_\_\_ edges. There are

n^{n-2} = 6^4

spanning trees!