---
tag: C10J2S8JB0
kind: concept
name: Cutwidth
aliases: [folding-number, minimum-cut-linear-arrangement]
sources:
  - wikipedia: en:69798178@r1329655861
    locator: Cutwidth
    note: adopted
    mention: wikipedia://en/69798178
    sections: [Summary]
same_as:
  wikidata: Q110772608
  wikipedia: Cutwidth
inventory: [88JPSVA1WH]
---

## Summary

In graph theory, the **cutwidth** of an undirected graph is the smallest [[integer|0C4JS9RF5M]] $k$ with the following property: there is an ordering of the vertices of the graph, such that every cut obtained by partitioning the vertices into earlier and later subsets of the ordering is crossed by at most $k$ edges. That is, if the vertices are numbered $v_1,v_2,\dots v_n$, then for every $\ell=1,2,\dots n-1$, the number of edges $v_iv_j$ with $i\le\ell$ and $j>\ell$ is at most $k$.