{"entities":{"Q2707974":{"pageid":2718713,"ns":120,"title":"Item:Q2707974","lastrevid":47594674,"modified":"2026-01-02T04:19:54Z","type":"item","id":"Q2707974","labels":{"en":{"language":"en","value":"On spanning trees and walks of low maximum degree"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1584474"}},"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":"Q2707974$857EF09E-2A35-4849-A09D-BF71D92824F8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"065720b5c1934a39c72be88a42fea82ac7645c53","datavalue":{"value":"0973.05023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2707974$2E7E9153-71D6-40C2-B83B-6AEB240CC268","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fadd1a6b49831546971c911e5695c4ecef3bf692","datavalue":{"value":{"entity-type":"item","numeric-id":202001,"id":"Q202001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2707974$3A24EC77-8699-42E3-A195-E939FD3DD3E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"06c6cdf9f9cc4fd22aa6bb2600b7dd6370a261f0","datavalue":{"value":{"entity-type":"item","numeric-id":202002,"id":"Q202002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2707974$C89B50B6-DDB4-405D-B3D5-3A6D5748ADE2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4cd6c78d17e8a8443dec489a5dbfd44e8bc13441","datavalue":{"value":{"time":"+2001-12-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2707974$B701E064-0ECF-4F25-92ED-3AD4E1FB42C6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2707974$539F7B1B-F2B6-4532-B1D1-AB15CD868CAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2707974$237A7AAB-DC97-4CF6-A06A-626AC6B8FA6A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5b7888addcab731a2f2adf41ad5c0fbd36e8698c","datavalue":{"value":"1584474","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2707974$AC2927C5-0A55-4BBB-9CF8-BF20BC0CE351","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"425fec25f1345f7b4ddbd44e571a6a48f40dfdaa","datavalue":{"value":"tree-minimal","type":"string"},"datatype":"string"},"type":"statement","id":"Q2707974$CBFC3938-C795-4149-95D3-F6D3DA562B42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9fdbdfd592c0e763114580dda7d11ac054e739c3","datavalue":{"value":"walk-minimal","type":"string"},"datatype":"string"},"type":"statement","id":"Q2707974$9032B2BC-30FB-4837-83F6-4346370F4E71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dae6b73647501cddc60bea81c63e58401d0164fd","datavalue":{"value":"Euler characteristic","type":"string"},"datatype":"string"},"type":"statement","id":"Q2707974$0DDEE0B2-23A9-42F2-9CAA-C37F7509CB12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"849b7a0d6519fee636943d9bde0b8b557d98cf60","datavalue":{"value":"spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q2707974$0069F527-C48D-4716-B1AD-0DDB7E185413","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"903a98ab6da5dec778e0b3ee7be200d39cc2b7db","datavalue":{"value":"spanning walk","type":"string"},"datatype":"string"},"type":"statement","id":"Q2707974$0139C082-BFF1-4F28-966C-2087B4176243","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e249ba6e5b3904c8883287728fdf3dc6af0ca4b0","datavalue":{"value":"discharging method","type":"string"},"datatype":"string"},"type":"statement","id":"Q2707974$5F27BC02-CCD4-4755-B872-9050A585986A","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":"Q2707974$779D0A9F-5A5A-4AD6-AF8E-68BBBA450828","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"60ecde349db9e2565075e503c730b4ba3c7a29ca","datavalue":{"value":{"entity-type":"item","numeric-id":5516076,"id":"Q5516076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2707974$C43080DE-1D34-48E7-A2F9-2FECD818C825","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b24cef5620710c92b18eb681dd4a2813e55510e5","datavalue":{"value":{"entity-type":"item","numeric-id":1802763,"id":"Q1802763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2707974$7B05AD0F-A161-4B42-8843-3178B083FA77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e6aae990a9760c8fac422311c7e531e543bc036","datavalue":{"value":{"entity-type":"item","numeric-id":1219294,"id":"Q1219294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2707974$259068FD-2811-4F66-B03B-485FDF2E1DB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0476fd93299a22e08cb0583e3c7f476899e864d4","datavalue":{"value":{"entity-type":"item","numeric-id":1898728,"id":"Q1898728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2707974$B3A68660-E493-405A-A061-C31C4B2836FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89a162c14589e72e9bc721c8d3c0e1d3a9aedef9","datavalue":{"value":{"entity-type":"item","numeric-id":2551470,"id":"Q2551470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2707974$21C6F104-9029-4639-A583-71A5EEBBB79F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77a782055bed0b58e863b1540839a5d718e5fa9a","datavalue":{"value":{"entity-type":"item","numeric-id":1338316,"id":"Q1338316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2707974$8F519DF5-5B62-4F4B-9C9C-EB49419BC0D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0fe02cfd8b0917d8df936aea1abb22648177dd69","datavalue":{"value":{"entity-type":"item","numeric-id":3353052,"id":"Q3353052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2707974$39707087-DA0D-43E4-AD8D-5526F9BA522D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f4ffead84d80034491ed16ea9eb28ada9a455c5","datavalue":{"value":{"entity-type":"item","numeric-id":2395458,"id":"Q2395458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2707974$26E2F9B4-C01B-4D5B-BFDD-B13F8009BD8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"22cc8febd4e183435b06aae790a0eb1069221743","datavalue":{"value":{"entity-type":"item","numeric-id":5341593,"id":"Q5341593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2707974$CFB8D1DA-EA40-4873-9362-DA6B3333F15B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"caa0725e5af2055939833ee9b6c407e502f468cf","datavalue":{"value":{"entity-type":"item","numeric-id":1127880,"id":"Q1127880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2707974$06837C17-E923-4138-80B4-53CC53653C22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16f8e6dfb51a257989e979830dc13fac9327fcd2","datavalue":{"value":{"entity-type":"item","numeric-id":1322007,"id":"Q1322007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2707974$49BD147A-2383-44ED-8166-0AE556CAC7C1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6c74ad41927b4a00372ac79e0c68c4e94e7cfa56","datavalue":{"value":{"text":"On spanning trees and walks of low maximum degree","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2707974$EB73B202-D61A-499A-A6FE-A6F4EDA248C7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4de5c7a5d238217ab4a071d198b3a40ee05be465","datavalue":{"value":{"entity-type":"item","numeric-id":2725046,"id":"Q2725046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2707974$56712F76-0784-4474-8879-F84ECE32B20C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2416c646d55d0e3098d27e9fa11a1e2085cb4d06","datavalue":{"value":"Let \\(\\chi\\) denote the Euler characteristic of a surface. Given \\(\\chi\\leq -36\\), a graph is called \\(\\chi\\)-tree-minimal if it embeds on a surface of Euler characteristic \\(\\chi\\), is 3-connected, has no \\([{8-2\\chi\\over 3}]\\)-tree, and is a graph on the fewest edges with this property. Given \\(\\chi\\leq -46\\), a graph is called \\(\\chi\\)-walk-minimal if it embeds on a surface of Euler characteristic \\(\\chi\\), is 3-connected, has no light \\([{6-2\\chi\\over 3}]\\)-walk, and is a graph on the fewest edges with this property. A graph is called \\(\\chi\\)-minimal if it is either \\(\\chi\\)-tree-minimal or \\(\\chi\\)-walk-minimal. It is shown that no \\(\\chi\\)-minimal graph has a triangle. Most results are proven by means of a generalization of a method of Tutte. But the main result, which states the best possible result that a 3-connected graph embeddable on a surface of Euler characteristic \\(\\chi\\leq- 46\\) has a spanning tree of maximum degree at most \\([{8- 2\\chi\\over 3}]\\) and a closed, spanning walk meeting at each vertex at most \\([{6-2\\chi\\over 3}]\\) times, is proven by means of a method defined here as discharging method. This is a technique developed to solve the 4-color problem. In the final part, an extremal class of well-known graphs, \\(K_{3,6-2\\chi}\\), is mentioned.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2707974$E95EED34-E6E7-45A1-8009-1A5E53880053","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"285a39053a84673e1b7757c4032e9ef7c9ebcaad","datavalue":{"value":{"entity-type":"item","numeric-id":394648,"id":"Q394648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2707974$8DFBAA7F-9159-4313-8645-83CE59AEC7AE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"62f0d8fe47a0c064c60aa6b949ae54b3fa1eaa46","datavalue":{"value":"10.1002/1097-0118(200102)36:2%3C67::AID-JGT2%3E3.0.CO;2-C","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2707974$6BD95BE8-6A6A-47B7-8A3A-9C693B1C735E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46bfb6b97eb0a5b887b314607c90377daf6c668b","datavalue":{"value":{"entity-type":"item","numeric-id":5300503,"id":"Q5300503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e25de4674dca0b188cb33289fb194cbccfb74fd","datavalue":{"value":{"amount":"+0.83266282081604","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2707974$457AA233-526B-44FF-901E-D7017BDB6F5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2a94776bd551fdddd6f007efe483188bbcd6ae3","datavalue":{"value":{"entity-type":"item","numeric-id":1333338,"id":"Q1333338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81b8131ffed7fc4e8be5ea9a2de0ae46dfbffa98","datavalue":{"value":{"amount":"+0.7933573126792908","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2707974$9872EF6E-58E4-4613-8E06-6D00E0A5CEA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d8c50bf449859469a1114e90efb436fff60de60e","datavalue":{"value":{"entity-type":"item","numeric-id":1127880,"id":"Q1127880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c962400869fd8d3051013ba1e89a793084bc6b1","datavalue":{"value":{"amount":"+0.7816254496574402","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2707974$50C1C063-2371-4C9D-A0DA-FD70CFE56306","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cdbadc29a4780ad7a60eb1998c9c961415d9543c","datavalue":{"value":{"entity-type":"item","numeric-id":1011698,"id":"Q1011698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d08fa5833804ba509db090f7e7862316e97dbf5","datavalue":{"value":{"amount":"+0.768244743347168","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2707974$AC48DAE9-3AB5-41A5-A5F4-6C58017533B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7383099212e6c5745249b534678ba77416d8234f","datavalue":{"value":{"entity-type":"item","numeric-id":1772196,"id":"Q1772196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad5c0b3dba1757cccd7a2317efea0a8a5be54296","datavalue":{"value":{"amount":"+0.7589658498764038","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2707974$AC1D9407-482E-417A-BAAA-53747EA7BFB4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2707974","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2707974"}}}}}