A short proof of Nash-Williams' theorem for the arboricity of a graph
type: Item
instance of: scholarly article
title: A short proof of Nash-Williams' theorem for the arboricity of a graph
zbMATH Open document ID: 0798.05042
DOI: 10.1007/BF01202467
author: Boliong Chen
author: Makoto Matsumoto
author: Jianfang Wang
author: Zhongfu Zhang
author: Jianxun Zhang
published in: Graphs and Combinatorics
publication date: 1994-05-10T00:00:00Z
review text: The authors give a self-contained short proof of Nash-Williams' formula \[ \rho(G)= \max_{H< G} \lceil q(H)/(p(H)- 1)\rceil \] for the edge- arboricity \(\rho(G)\) of a graph (with possible multiple edges but no loops). Here \(H\) runs over all subgraphs of \(G\) with \(p(H)= \# V(H)> 1\) and \(q(H)= \# E(H)\). The proof easily follows from the following lemma which is proved in detail. Lemma: Let \(G\) be a connected arboricity critical graph with \(p(G)> 1\). Then for any \(e\in E(G)\), any \((\rho(G)-1)\)-forest decomposition of \(G-e\) is a decomposition into \(\rho(G)-1\) spanning trees of \(G\).
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 567481
zbMATH Keywords: Nash-Williams' theorem
zbMATH Keywords: edge-arboricity
zbMATH Keywords: decomposition
zbMATH Keywords: spanning trees
MaRDI profile type: Publication
cites work: Q4696619
cites work: Edge-Disjoint Spanning Trees of Finite Graphs
cites work: Decomposition of Finite Graphs Into Forests
Recommended article: Q4696619
Recommended article: An enhancement of Nash-Williams' theorem on edge arboricity of graphs
Recommended article: A short proof of Brooks’ Theorem for vertex arboricity
Recommended article: NASH‐WILLIAMS’ THEOREM ON DECOMPOSING GRAPHS INTO FORESTS
Recommended article: Q3340901
Recommended article: A note on the arboricity of graphs
Recommended article: Short proofs of theorems of Nash-Williams and Tutte
Recommended article: A short proof of a theorem on degree sets of graphs
Recommended article: A graph-theoretic proof of arrow's dictator theorem
Recommended article: The Nash-Williams conjecture and the dominating cycle conjecture
description: scientific article; zbMATH DE number 567481