{"entities":{"Q1328385":{"pageid":1339135,"ns":120,"title":"Item:Q1328385","lastrevid":67180152,"modified":"2026-04-12T15:50:20Z","type":"item","id":"Q1328385","labels":{"en":{"language":"en","value":"Subtrees and subforests of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 599861"}},"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":"Q1328385$AE9EB98A-5443-450A-9696-3F404EF1EE12","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"726b8ec24b0d2383c4f31c93d788fef9612b8c07","datavalue":{"value":{"text":"Subtrees and subforests of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1328385$E9559A35-E9A4-4181-AA61-E9C48D660EF9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"31362a13c2e7d93a34da6a7d6f3a3fdb723c0563","datavalue":{"value":"0804.05024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1328385$C3200A4E-4EDA-4EE3-AAF7-4076D7B46684","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"35fe75700063d91d5aa0430b9cbc603605f8dc13","datavalue":{"value":{"entity-type":"item","numeric-id":383768,"id":"Q383768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1328385$18A384C6-9F2B-488A-9EF5-2B80AF3E1EC7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1328385$C739E384-6179-4128-BCD0-4D4D9CE0A207","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2a8ab64d0488bf8097fa6605cadee4d59b47e319","datavalue":{"value":{"time":"+1995-01-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1328385$A2DC8EFA-3E90-45ED-871C-89CC85D9EA67","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"63e66a5102f6bd970888421611cf84ead544bb8c","datavalue":{"value":"Let \\(G\\) be a finite, simple graph. Let \\(| G |\\), \\(e(G)\\), \\(\\Delta (G)\\), and \\(\\delta (G)\\) denote respectively the order, size, maximum degree, and minimum degree of \\(G\\). For two positive integers \\(k\\) and \\(n\\) \\((>k)\\) set  \\[ f(k,n) = \\max \\left\\{{2k - 1 \\choose 2}, {k - 1 \\choose 2} + (k - 1) (n - k + 1) \\right\\}. \\]  A graph \\(G\\) is said to contain a graph \\(H\\) if \\(H\\) can be embedded in \\(G\\), i.e. \\(G\\) contains a subgraph isomorphic with \\(H\\). The author gives elegant proofs to the following two theorems.   Theorem 1. Suppose \\(G\\) is a graph of size \\(e(G) > f(k,n)\\). Then \\(G\\) contains every forest on \\(k\\) edges without isolated vertices.   Theorem 2. Let \\(r\\) be a positive integer. Suppose \\(G\\) is a graph of order \\(n \\geq r^ 2 - r + 1\\) with \\(\\Delta (G) = n - 1\\) and \\(\\delta (G) \\geq n - r\\). Then \\(G\\) contains all trees of order \\(| G |\\).   Theorem 1 answers a long-standing conjecture (posed in 1963) of Erd\u0151s and S\u00f2s in the affirmative. Theorem 2 improves a result due to \\textit{R. J. Faudreee}, \\textit{C. C. Rousseau}, \\textit{R. H. Schelp} and \\textit{S. Schuster} [Isr. J. Math. 35, 177-185 (1980; Zbl 0436.05020)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1328385$9B93E7E2-FAF7-4FEA-8C59-26889886839A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1328385$E3903271-AE6C-4970-AE39-5E9820583BCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1328385$C9DBD99A-0830-496E-820E-C9088C08125A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1328385$B29EEEAA-378D-40A1-9B2E-100906B5F46B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2b093012ceb014a8b0c913c459bc28e17c7bc01a","datavalue":{"value":"599861","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1328385$1A3790AD-998F-4F86-9CCE-7E8164F7C138","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e86d9b4ad5a06064fd9c9bcbc50f8026b1c776dc","datavalue":{"value":"embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1328385$6184F4C1-EDE5-467B-809C-4E543DDBC6F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e87bb1aed89f5da6ee5d1aa38eb687932a17c03","datavalue":{"value":"subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1328385$3C87B9C3-1AF4-4818-929D-19292DDA66F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc79eafc1d9ceb1ab79797a36449e9df369395df","datavalue":{"value":"forest","type":"string"},"datatype":"string"},"type":"statement","id":"Q1328385$E9C54766-8EBD-436F-A2F9-29BBAC4751C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c24938459dbf20196734dcf6c3a35c8a8724abee","datavalue":{"value":"trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1328385$4A794F67-BABD-4EE1-B396-E3CE52A44EEE","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0dfbdb0929ddc22bcd5bd1c182b95d3875d4d630","datavalue":{"value":{"entity-type":"item","numeric-id":1164054,"id":"Q1164054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1328385$B689DA9E-B213-4BCE-AB29-5F873B400093","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":"Q1328385$E3E6F287-F330-41F0-A3F5-05FD80AFC27F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3e4ceaaaa71a69b1161e98785c888d742f60f2c2","datavalue":{"value":"https://doi.org/10.1006/jctb.1994.1030","type":"string"},"datatype":"url"},"type":"statement","id":"Q1328385$151BD5E8-9DBF-40D5-8E99-C311ABA5C3E5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"200e478465c1a0b51736a8b276a07ebd2837afb7","datavalue":{"value":"W2049309804","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1328385$9E2ADBF7-A7D7-42E9-ADE6-7B512B4D25FB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d264e70089702ddf22c251ed5764783c1e3e9a36","datavalue":{"value":"10.1006/JCTB.1994.1030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1328385$3C1BA641-275E-47E3-A7E4-243C7AD962C0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cb7135d7dcb62be1885d7b0c214958600c0312f8","datavalue":{"value":{"entity-type":"item","numeric-id":4552186,"id":"Q4552186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8be8dbf787f5d24c5ba6210801b81fda0701b110","datavalue":{"value":{"amount":"+0.8646635","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1328385$83C7EFEC-861A-4244-84AF-1A24974AA85D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b58a3894259881fb0138c8e73114137950c8aa98","datavalue":{"value":{"entity-type":"item","numeric-id":1898723,"id":"Q1898723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec72a1b699efceb2219e2f5e7ae8ef1acc4ee742","datavalue":{"value":{"amount":"+0.84918857","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1328385$0F9122B8-8E80-4E43-A267-A7FDC8D7C341","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e33a0c882b60f2454ae649874208e4f5f7ad1379","datavalue":{"value":{"entity-type":"item","numeric-id":1362105,"id":"Q1362105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c7dcdb412829c7a7b0bc14fd1c33e3840e102372","datavalue":{"value":{"amount":"+0.8476258","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1328385$9ED0330C-A5BA-4D54-A959-EEA71DC235DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab9af5c46120e2668a3e1da2ce9d703fe3fdb6f1","datavalue":{"value":{"entity-type":"item","numeric-id":4865531,"id":"Q4865531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b5c871790425c44a596977395933fec4e410dc97","datavalue":{"value":{"amount":"+0.844742","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1328385$0BE4C57D-B433-44D4-8399-170337D2C4D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c26d7853e820930b2901d6e8703f6709c12e1ea3","datavalue":{"value":{"entity-type":"item","numeric-id":540102,"id":"Q540102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74e4780e59639af30e1d6ebe544134c77c72e784","datavalue":{"value":{"amount":"+0.83612084","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1328385$3A56770E-D6C2-4674-912B-AE3155CDA475","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f1c2d6e2492dfd38f02629264c26128e93bb97db","datavalue":{"value":{"entity-type":"item","numeric-id":2581630,"id":"Q2581630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"195ab6e2b3e2a2c3e215bf46c27edbf5acffb075","datavalue":{"value":{"amount":"+0.8307797","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1328385$84C70041-A673-40B6-B694-3053BD70EFBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"317e1d6e5dda067a476b383d7a2798c867296541","datavalue":{"value":{"entity-type":"item","numeric-id":1567289,"id":"Q1567289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1e2df7970598499eb32a825c0db1a7b54fa7a55","datavalue":{"value":{"amount":"+0.82777953","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1328385$70F0C50C-87C6-4789-AF53-7C1EDB8D2076","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15dcc5b5709f48641f8ec60696701974bc14344c","datavalue":{"value":{"entity-type":"item","numeric-id":1916132,"id":"Q1916132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4c168881664de8b4a616373fcb1df1af2818d89","datavalue":{"value":{"amount":"+0.8248689","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1328385$83A5C686-F485-4EC4-B689-C417C360BE21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9a372ed675dced2678ea27972c1d2590b0ec2cc","datavalue":{"value":{"entity-type":"item","numeric-id":2741374,"id":"Q2741374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6de0b713b667d010c3ef7b3565880c8fa56b6177","datavalue":{"value":{"amount":"+0.8221643","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1328385$1DF8DD77-D198-4F0A-A834-A828E0EC5ABF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"87b87b417f6bac31581097af8427512ba73b5d92","datavalue":{"value":{"entity-type":"item","numeric-id":5434262,"id":"Q5434262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e12fef1d87676ca57f93d2429dedd5083127f88","datavalue":{"value":{"amount":"+0.82071006","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1328385$A4153A37-3C5B-4DF0-A65F-EBCFDE9F9488","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Subtrees and subforests of graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Subtrees_and_subforests_of_graphs"}}}}}