| ▲ | usrusr 7 hours ago | |
"Any sufficiently sparse graph is indistinguishable from a linked list" comes to mind ;) | ||
| ▲ | gowld 5 hours ago | parent [-] | |
A linked list is sparse by the metric of minimum maximum degree (2). A maximally sparse connected graph by mean (degree edge/node ratio) is any tree (mean degree ~ 1), not necessarily a linked list. | ||