All trees contain a large induced subgraph having all degrees 1 (mod \(k\)) (Q1377743)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | All trees contain a large induced subgraph having all degrees 1 (mod \(k\)) |
scientific article |
Statements
All trees contain a large induced subgraph having all degrees 1 (mod \(k\)) (English)
0 references
6 July 1998
0 references
It is proved that for \(n\geq 2\) and \(k\geq 2\) every \(n\)-node tree has an induced subgraph with at least \(2\lfloor(n+ 2k-3)/(2k- 1)\rfloor\) nodes, such that all nodes in this subgraph have degrees congruent 1 modulo \(k\).
0 references
subgraph enumeration
0 references
tree
0 references
