{"entities":{"Q5906272":{"pageid":8018769,"ns":120,"title":"Item:Q5906272","lastrevid":97731314,"modified":"2026-06-05T15:18:53Z","type":"item","id":"Q5906272","labels":{"en":{"language":"en","value":"Three-regular subgraphs of four-regular graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1199957"}},"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":"Q5906272$22C548D3-7E58-4319-8D3D-06710D8A91EE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c00ec34465b245c18c79b8d5fe001b98be113e7c","datavalue":{"value":{"text":"Three-regular subgraphs of four-regular graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5906272$A2978F97-FB53-47DC-A2A6-5D062DF85002","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1cc96d481c6518877b3cf307a73f5ea275ff3744","datavalue":{"value":"0907.05048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5906272$76C352C6-75E0-4589-A679-2961527D2881","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"322c0e19900d2907b7cf14e0a96cb6b83e42a941","datavalue":{"value":{"entity-type":"item","numeric-id":1103004,"id":"Q1103004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5906272$A0206A9D-2FC5-4AD7-964A-7ED6BF46B5B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4781c95952d667dea14a694c6e75f5faac1f09b2","datavalue":{"value":{"entity-type":"item","numeric-id":1266393,"id":"Q1266393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5906272$E24C03D8-D502-4032-88D0-14E049BEAE48","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5906272$76DCAF5E-8D30-4E77-AA8E-063F4F22DAFB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ffb3dc1e9130e9040b0066185c9155bfd302f50c","datavalue":{"value":{"time":"+1998-10-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5906272$A40D20BB-11CC-49BC-81E0-E224E08FC318","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a805dd05fe1f9973b268ec8bcf57215ed1550730","datavalue":{"value":"It is known that any simple 4-regular graph contains a 3-regular subgraph. In the present paper the authors consider finite undirected graphs with multiple edges but without loops. They extend the above given result to such 4-regular graphs \\(G\\). They use the concept of Euler orientation defined as follows: Let \\(G= (V,E)\\) be a 4-regular graph with \\(v_i\\in V\\), \\(| V|= n\\), \\(| E|= 2n\\). Then an Euler orientation of \\(G\\) is a partition \\(E= \\bigcup^n_{i= 1} A_{v_i}\\) of the set \\(E\\) of edges such that \\(A_{v_i}\\) and \\(A_{v_j}\\) are disjoint for any \\(i\\neq j\\) and each \\(A_{v_i}\\) has exactly two edges both incident with \\(v_i\\). \\(N= N(G)\\) denote the number of Euler orientations of \\(G\\).   The main result of the paper is Theorem 2.2: A 4-regular graph \\(G\\) with \\(n\\) vertices has a 3-regular subgraph if \\(N\\not\\equiv 1\\pmod 3\\). This theorem is extended to Theorem 2.3: A \\(2m\\)-regular graph \\(G\\) has a \\(p\\)-regular subgraph (\\(p\\) a prime such that \\(p- 1\\leq m\\)) if \\(N\\not\\equiv 1\\pmod p\\).   Further a set of 4-regular graphs with multiple edges is given which have no 3-regular subgraphs but for which the authors know exactly the number \\(N\\) of Euler orientations. Finally a conjecture of Thomassen is reduced to 4-regular graphs only with multiple edges. It asserts that any 4-regular connected graph with an even number of vertices has a 3-regular subgraph. This has been proved by the second author.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5906272$460D1D6B-973B-4DE0-B4CD-1A2F4183176D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5906272$45E1E3A9-7D8D-490D-9F31-094531A07D54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5906272$21FB5F24-BB7C-4E43-A59B-4C5A6CC99E98","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8dd8dc2bb9c57c1847d3c1abd34b35cd89b58f2e","datavalue":{"value":"1199957","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5906272$48ED84D7-C69A-4921-91A4-89B4F5745FA9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f18758ebe1128579b8963c569324c28caa13169c","datavalue":{"value":"Euler orientation","type":"string"},"datatype":"string"},"type":"statement","id":"Q5906272$2944B9D0-9B7F-449D-B17B-23CA77E7C557","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e41fb471c5632503b8716f23269ac7a1a49e160e","datavalue":{"value":"partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q5906272$7FCD45FF-0107-4F46-9D51-59380C181D37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"96a5cae47ba93f8d664444333ef45db183a6d7a7","datavalue":{"value":"conjecture of Thomassen","type":"string"},"datatype":"string"},"type":"statement","id":"Q5906272$BB9C3D1B-60CE-4E9F-8D4B-C863632E909F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"31cef456e8646accdc28b523a232a52220366047","datavalue":{"value":{"entity-type":"item","numeric-id":593309,"id":"Q593309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5906272$8AFDD92E-220E-425B-A1B4-E762CE910420","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":"Q5906272$C4152C4D-542A-4FF2-BBAC-6781A61987D2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c05db50c49bd643a35502a9548939d845403179c","datavalue":{"value":"https://doi.org/10.1006/eujc.1997.0150","type":"string"},"datatype":"url"},"type":"statement","id":"Q5906272$19DF855F-8A88-4466-833F-72521814F1BB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"80e94f9a2d6ef7ca912abf4e9382c18e9d4f1b70","datavalue":{"value":"W2043546239","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5906272$ECA93886-FF90-4091-A674-BE63310F4601","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b9d5b4bedc6cb38c18659e2fe31602a7ebebc932","datavalue":{"value":"10.1006/EUJC.1997.0150","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5906272$667284B0-F099-4117-B8AC-136D01F98FC7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e5368eae45fc92aa25c3874b469192a74fa0ab5","datavalue":{"value":{"entity-type":"item","numeric-id":4314371,"id":"Q4314371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"611f906772b015686c5e6c320c7f8099611eb010","datavalue":{"value":{"amount":"+0.8710159659385681","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":"Q5906272$DCD464C5-02EE-4A7B-B9C9-AFE81A8556E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46b632537db4a1267eabf3dfa86c60e247f692dd","datavalue":{"value":{"entity-type":"item","numeric-id":3680871,"id":"Q3680871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d11c256c93074f6e54582b71be34298117b289cf","datavalue":{"value":{"amount":"+0.8456305265426636","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":"Q5906272$8F77161F-89DD-448A-A625-1025652B44D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c45535669996bfe25cc6437b540cb42263e86471","datavalue":{"value":{"entity-type":"item","numeric-id":4954421,"id":"Q4954421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc5fab744296126f53010051c3d44773ebe57893","datavalue":{"value":{"amount":"+0.8437496423721313","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":"Q5906272$92500B11-1E17-4474-AB54-6BBC1C0987F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b51d0417f70bf51b2f8e026c91f8fb3d97ea523","datavalue":{"value":{"entity-type":"item","numeric-id":5264756,"id":"Q5264756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4890f94e3f063ece16dae87de83041f1fd4d2ee","datavalue":{"value":{"amount":"+0.803808331489563","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":"Q5906272$31AC2237-9D06-4D1E-ABFB-8A20786683D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5098a3aa13c0076bdb5dd5120e2f4b6742433c9c","datavalue":{"value":{"entity-type":"item","numeric-id":1813087,"id":"Q1813087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a129a90ce966de19c58dc9c136da0ab61630bb58","datavalue":{"value":{"amount":"+0.8001038432121277","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":"Q5906272$7407049D-F0FF-4D79-AEE4-D13F72A02045","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Three-regular subgraphs of four-regular graphs","badges":[]}}}}}