{"entities":{"Q2161306":{"pageid":2172049,"ns":120,"title":"Item:Q2161306","lastrevid":72752397,"modified":"2026-04-14T07:32:21Z","type":"item","id":"Q2161306","labels":{"en":{"language":"en","value":"Every graph contains a linearly sized induced subgraph with all degrees odd"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7567805"}},"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":"Q2161306$6048DEB0-4681-4043-8507-1F031AC5AA54","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ce3d040d4dd8ecbb8890ac41511a1e9891334f7a","datavalue":{"value":{"text":"Every graph contains a linearly sized induced subgraph with all degrees odd","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2161306$A5C1C961-2ACA-4237-B92F-DE6F11A72306","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ac342e503494f3302f699b24e59af999d1b7bb4b","datavalue":{"value":"1501.05023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2161306$99E2752C-DD37-40F5-8DC5-CB5EB95EDD8F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"36f23551e9e93e966d7bef0515d13918e4cfe3ad","datavalue":{"value":{"entity-type":"item","numeric-id":247214,"id":"Q247214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2161306$52D4E0BC-CBC3-4DED-9309-5FE35FB930F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b1cf400bc99a406c4d5dfcfdd4d04f10c4dc1f7f","datavalue":{"value":{"entity-type":"item","numeric-id":178700,"id":"Q178700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2161306$BCFC18AE-8576-4F10-94FF-ECD8A271D4B9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"87fedd43d9515b94c7651de65777aba7be17422f","datavalue":{"value":{"entity-type":"item","numeric-id":165833,"id":"Q165833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2161306$E4D3CC01-79AC-4164-96D3-2D708EB3AA22","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"563dfd2d7fe5e800709347107faac54b2d997517","datavalue":{"value":{"time":"+2022-08-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2161306$AD007E5D-CF07-4555-852A-152AB09B2FDD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9c781224eb8c97d763a1e5e8f8e8fc93307582d9","datavalue":{"value":"https://arxiv.org/abs/2009.05495","type":"string"},"datatype":"url"},"type":"statement","id":"Q2161306$03BBA51E-331B-478C-B731-DA7DF2B34031","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"89a31374dc9e1bf00dc65b6f6e1f7412363c7609","datavalue":{"value":"Let \\(G=(V,E)\\) be a graph on \\(n\\) vertices with no isolated vertices. Let \\(f_o(G) = \\max \\{|V_o|:G[V_o]\\text{ has all degrees odd}\\}\\) and let \\(f_o(n) = \\min \\{f_o(G) : G\\) is a graph on \\(n\\) vertices with \\(\\delta(G) >1\\}\\). A well-known conjecture is the following. There exists a constant \\(c >0\\) such that for every \\(n \\in \\mathbb{N}\\), we have \\(f_o(n) \\geq cn\\). \\textit{Y. Caro} [Discrete Math. 132, No. 1--3, 23--28 (1994; Zbl 0808.05090)] proved that \\(f_o(n)= \\Omega(\\sqrt{n})\\). Later, \\textit{A. D. Scott} [Comb. Probab. Comput. 1, No. 4, 335--349 (1992; Zbl 0793.05089)] improved this to \\(f_o(n) = \\Omega(n/ \\log n)\\).  In this self-contained paper, the authors establish the validity of this conjecture with \\(c=1/10,000\\). They comment that this constant is not optimal.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2161306$DDF0CBA0-9156-42C6-8007-D4D2BF989D2C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2161306$9755732F-FE6A-402C-8CBA-94EF37D5E354","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"245985807b016d115d4f4ba6c61b278b3497fcff","datavalue":{"value":"05C07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2161306$A82B00E8-6827-4D68-8D93-B4D1B26A369B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2161306$B8A8D6CE-9753-456E-A806-A922C0814AAD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"095c5643b96704f93a8dae538711651b47e1bced","datavalue":{"value":"7567805","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2161306$28339D24-BC35-4DB9-8E29-24C812835F28","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"63c2a8d5405a961a6ea7cd3b86ee7b77737d9d38","datavalue":{"value":"odd subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2161306$7613E0C7-408C-4FD1-920C-463274AEC509","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90c74891cec8401966710b227ddb5fd4172ceeae","datavalue":{"value":"Caro's conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q2161306$FA5229C4-ABBE-4872-B642-D2F70417B0EA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"bc64db3aecebe4824aaa24fcca35fb658aef4364","datavalue":{"value":{"entity-type":"item","numeric-id":418888,"id":"Q418888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2161306$49C93450-4AD2-4648-AFDC-58748E061BDB","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":"Q2161306$A9786F8B-3598-427A-BA77-9D5039E3D8F8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"48bfc2bdc452a619054ccaa8fef5ee5ea039264c","datavalue":{"value":"W3084441407","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2161306$45E3D767-EFF5-48DD-8AD9-7E4460CC04EE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"67217bfffed0068399799c360151131444533e63","datavalue":{"value":{"entity-type":"item","numeric-id":1336646,"id":"Q1336646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2161306$D0000E00-8A6A-46C3-8FFD-11BD59723A04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a710b7359cc1f9233711666338c1335fba582f97","datavalue":{"value":{"entity-type":"item","numeric-id":4276003,"id":"Q4276003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2161306$0FEBF435-87FD-4A50-9501-5DD06629BF1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d355f975a0318652d523024cde7a39659ebee39","datavalue":{"value":{"entity-type":"item","numeric-id":4291193,"id":"Q4291193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2161306$875C48C0-1B4C-4CDE-891C-9682A0937251","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94eedd9dbc44fc59776c33c1ccd9d5cba21c0640","datavalue":{"value":{"entity-type":"item","numeric-id":5952391,"id":"Q5952391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2161306$479A301B-3CEE-45F1-B3A3-A35B49C1DE54","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f0d09317f87ab501ac3d12743e5aed369ecbafbe","datavalue":{"value":"10.1016/J.AIM.2022.108534","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2161306$26EA8CF7-1895-49C2-B65F-5A36BA75F830","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"230dbd59d7b9f2025f79a265d21f04ce3a60708e","datavalue":{"value":{"entity-type":"item","numeric-id":1336646,"id":"Q1336646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c4ac69e100e45e5fe54843f902525a12f3e38c0","datavalue":{"value":{"amount":"+0.900550365447998","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":"Q2161306$A13CD5F7-74C7-4F04-9011-AC27CAC67A5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54a8182d9bb761c45972b5cf05fecb4277200c81","datavalue":{"value":{"entity-type":"item","numeric-id":4291193,"id":"Q4291193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"161b2eec53cd9185dfa35a3af36e942ba4e022a2","datavalue":{"value":{"amount":"+0.8759877681732178","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":"Q2161306$064CE4A2-138E-4FAF-AE9C-2F7976A2C267","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f8f5611a4e90e6614f79b89e71201cd89bfcc58","datavalue":{"value":{"entity-type":"item","numeric-id":1893180,"id":"Q1893180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4af94f645886ffac5f85ac90eaedd4126b9eda16","datavalue":{"value":{"amount":"+0.8508120775222778","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":"Q2161306$41C374DE-E40E-4824-8F73-FD77E451F648","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"80861cff91fd0d766e2a6e304de100055b109250","datavalue":{"value":{"entity-type":"item","numeric-id":1322256,"id":"Q1322256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"970b8bbba240617b851b6bd02201ff111f218ffb","datavalue":{"value":{"amount":"+0.8267809748649597","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":"Q2161306$B9B19813-7F82-4F33-A242-D12B8F8BFB37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f737a334e82cb2a5908b124d10c14b306bedfe4","datavalue":{"value":{"entity-type":"item","numeric-id":2672043,"id":"Q2672043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ffdc9aef18f604d29753d626024512b8d63bd0f2","datavalue":{"value":{"amount":"+0.8048271536827087","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":"Q2161306$DE0E2B15-C569-478D-A2DA-F26EF282D83F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Every graph contains a linearly sized induced subgraph with all degrees odd","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Every_graph_contains_a_linearly_sized_induced_subgraph_with_all_degrees_odd"}}}}}