{"entities":{"Q1323488":{"pageid":1334238,"ns":120,"title":"Item:Q1323488","lastrevid":43031080,"modified":"2025-07-17T01:39:59Z","type":"item","id":"Q1323488","labels":{"en":{"language":"en","value":"A short proof of Nash-Williams' theorem for the arboricity of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 567481"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323488$4870A48F-F5DD-48AC-9E2D-342A1E0801CF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e60ee606cc303278977b5075b01fa0c7014ca9a2","datavalue":{"value":{"text":"A short proof of Nash-Williams' theorem for the arboricity of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1323488$26556517-1576-433F-8815-E65ABF968727","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"657cf2225526d7bd9bd0c5de19d9c042e8e33009","datavalue":{"value":"0798.05042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323488$AA2C3CB5-790D-48FA-90D6-661E4AE85111","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e5ef5a42b7fbeae85232b50839e955537154501e","datavalue":{"value":"10.1007/BF01202467","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323488$97B14BC2-84AA-4721-B161-076C289E0708","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ed1f6638c854194bdde52fa2e99c543b8abee06f","datavalue":{"value":{"entity-type":"item","numeric-id":1323487,"id":"Q1323487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323488$4CCD1ED7-3A5F-44BD-9A65-F7E9BCFBC13B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9bd54a7b257f44eba4d98b5778d7ee91b88cf0dc","datavalue":{"value":{"entity-type":"item","numeric-id":810545,"id":"Q810545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323488$00D23B39-2AE9-4B4B-B68F-534542626183","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b15d630adaf85dfdfa755ae0f18ad0eea602f4fc","datavalue":{"value":{"entity-type":"item","numeric-id":1753345,"id":"Q1753345"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323488$56C05CDA-5109-4D48-A84C-A76EBC674844","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7e48c254d63da6ffd6eedc48d191fd3de5005716","datavalue":{"value":{"entity-type":"item","numeric-id":221702,"id":"Q221702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323488$0EA90A60-6AE8-499A-A3BD-22D9CD31807A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ab1133bad0a0a94f559300c78a94b266f0b636df","datavalue":{"value":{"entity-type":"item","numeric-id":1629592,"id":"Q1629592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323488$376888A4-86D6-45A0-836B-77E25362851D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323488$60E8C788-0F78-4294-9133-EC260BD52896","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2eea7eb210317162e8ade44c06f241e090fd5838","datavalue":{"value":{"time":"+1994-05-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1323488$B40F3756-ED6A-4BB5-9105-B1FAD2E1845E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"01a6b5e53afd61120f6476586eeb0e6a59640894","datavalue":{"value":"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\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323488$CD92C689-2F05-485E-BA3C-97E8DFC267CF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323488$EDAC03C8-2566-4CC6-B056-CB42579BFA46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323488$18680ED9-3D31-4F09-8635-9291A4560912","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d27b162e475b2a508749cbdbdf8ddd5512fefd90","datavalue":{"value":"567481","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323488$CFC22DDC-2303-4DB7-B465-5AB7DF2F2885","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5b6c84be86d5ff400590f70dfaf2a4a59d17f20a","datavalue":{"value":"Nash-Williams' theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323488$98762728-2612-4296-ACAD-631DF4E7DA52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3dbdb3134f578ed393790acd4b4b4b13095eefc7","datavalue":{"value":"edge-arboricity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323488$4A41C9C1-4773-4C83-A4AF-7AF7716E32C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"615f2a3773e3a9a3bad386a540fbc6c58cfa22ee","datavalue":{"value":"decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323488$65651677-CF7D-47F3-90E1-2CAB0FBE03AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"79fea923fe257428a15567ac9a4393a98e6d9e26","datavalue":{"value":"spanning trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323488$715D1EB2-6977-422A-8EAC-7B50BE44CD92","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323488$C1209C83-4F3D-4A0E-A08F-E152E2483EC9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"356384fb939dc1ec7f4b1b19394c89810613e5bc","datavalue":{"value":{"entity-type":"item","numeric-id":4696619,"id":"Q4696619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323488$773E5842-48FB-4A3F-B372-9C173452D67D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"711cb68a3f23253ea3bfc5d62858e204e53a49ca","datavalue":{"value":{"entity-type":"item","numeric-id":3286077,"id":"Q3286077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323488$CB3EA495-8461-43F5-A89C-5F1B2113A6FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79f40f6cac0c780a9b93fef04ad01fbee5da55dc","datavalue":{"value":{"entity-type":"item","numeric-id":5731396,"id":"Q5731396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323488$96F779DD-1AC2-4CCC-89BB-4E33A61B793D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"86121cc3ed50f18e34f9ece185e7fb2b57a6f7ca","datavalue":{"value":{"entity-type":"item","numeric-id":4696619,"id":"Q4696619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"423836c0c1e2fedebdf1d347446338f94ab18e37","datavalue":{"value":{"amount":"+0.9675212","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1323488$AFA59282-9BA8-485E-BEA3-64A15CC58F97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad82dc3d31f6778bfa5e07a7bd0fda8b71886656","datavalue":{"value":{"entity-type":"item","numeric-id":1750785,"id":"Q1750785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"296571f457f93882b9510048fbc1c73a3a48bfe4","datavalue":{"value":{"amount":"+0.9298881","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1323488$13EC661A-27C1-454F-8F51-9BC88C0747B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0538efeccfd6bed29f495db63c66b210d71c41dd","datavalue":{"value":{"entity-type":"item","numeric-id":5154607,"id":"Q5154607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"faf0ad18aba87ef72da47e6480f04dd5346e72de","datavalue":{"value":{"amount":"+0.91874087","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1323488$36CC1D43-E7A0-4638-9CB9-757592AE9383","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4a97d383d30875658daa2b215fe41817e136cd0","datavalue":{"value":{"entity-type":"item","numeric-id":3191152,"id":"Q3191152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c426937cd0e41bd12caaf611d70d1a0c418dd1cb","datavalue":{"value":{"amount":"+0.88565594","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1323488$7F69CD30-EB3C-4C73-8FFA-7679CA8E5C43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"28448e70b692481355f2e4009874cd19d1b90897","datavalue":{"value":{"entity-type":"item","numeric-id":3340901,"id":"Q3340901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2480eec0de34c1d043bccdd65ecf9e99d163817b","datavalue":{"value":{"amount":"+0.8814867","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1323488$D6E435EE-C102-4C3C-AE51-E5C0DE3750D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c58736ab44f255a9ffeb85ff1f3b822e60adabc","datavalue":{"value":{"entity-type":"item","numeric-id":1205341,"id":"Q1205341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b5759a9448e2fd296609169646168e1f8d98f179","datavalue":{"value":{"amount":"+0.88081545","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1323488$43F76D11-7FF6-4E95-842A-83B2A41A74B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e2989531652e55b0703ea4b1c3657ebbf839b76","datavalue":{"value":{"entity-type":"item","numeric-id":2713657,"id":"Q2713657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5dc82d5143609c2b4e96000199b8b00b1395c287","datavalue":{"value":{"amount":"+0.87579703","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1323488$9CEE8613-884B-4B33-AC50-B5B69B5A0A8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea2d338c01fd420bc7ea70cb86dbeb1b6e9cf4c0","datavalue":{"value":{"entity-type":"item","numeric-id":875603,"id":"Q875603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c254c593901b28a445fdfebb2976e49fd64ab1fd","datavalue":{"value":{"amount":"+0.871752","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1323488$C6BA2C1A-7E00-40A8-9109-4342C95C73DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56a4d3e60819e541e7917b53925796079db88973","datavalue":{"value":{"entity-type":"item","numeric-id":1206216,"id":"Q1206216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"834ec338d6fb1a40799ed60d436fc90f0fbeaf40","datavalue":{"value":{"amount":"+0.86314654","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1323488$8D131604-9312-4E4B-91E4-CE0F6FE9CC66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bdee40e70c8c21290ab48058e8546d156219e269","datavalue":{"value":{"entity-type":"item","numeric-id":2309214,"id":"Q2309214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26f051fb13fc5bba05c3c6dbce5e9009813b6a0f","datavalue":{"value":{"amount":"+0.86253726","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1323488$FBEC8F9F-321C-4F5E-8307-A88C9ECD37A4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1323488","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1323488"}}}}}