{"entities":{"Q1106857":{"pageid":1117606,"ns":120,"title":"Item:Q1106857","lastrevid":69654975,"modified":"2026-04-13T08:29:41Z","type":"item","id":"Q1106857","labels":{"en":{"language":"en","value":"Extremal 3-connected graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4063121"}},"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":"Q1106857$1FD4471E-C3A7-4F98-83D0-85D6BDE22989","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9a2f2a9c8b2e8c893cdda86ee0e623b573f351c1","datavalue":{"value":{"text":"Extremal 3-connected graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1106857$E390871C-8851-4F91-BA51-458988906A7A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7662bd2496f4f37808b8971b5968695f33a330bc","datavalue":{"value":"0652.05028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106857$23DF0869-9298-4883-9264-30D445777733","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e3c1a2468f33774d660c460c2cbfd23aae4d556f","datavalue":{"value":"10.1016/0012-365X(88)90117-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106857$5B1E0386-37BD-42B3-9E54-49E997064B8B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"eb60b8d918936ffdb2c353fc0cd93cf62f2a7514","datavalue":{"value":{"entity-type":"item","numeric-id":583083,"id":"Q583083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106857$01D2533B-4229-4645-8273-D7B6D53B914F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106857$25087A76-F7FC-46A9-A2E4-A59FA9334403","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1106857$45D2A7A6-5E8A-4DB8-BBB7-AB91DDE34D11","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2fc22b2a6dd60dea37e3e1bf5dc5c4deeb576b38","datavalue":{"value":"Theorem 2: Let G be a 3-connected graph with minimum degree at least d and with at least 2d-1 vertices. Then for any 3 distinct vertices x, y, z there is a path from x to z through y and having length at least 2d-2. Furthermore, suppose that G has at least 2d vertices, that no set of exactly d vertices meets every edge and that for every vertex \\(v\\neq x\\), z, G-\\(\\{\\) x,v,z\\(\\}\\) has a component which is not a complete graph \\(K_{d-2}\\). Then there is a path from x to z through y and having length at least 2d-1.    From the proof of this theorem it follows that there are only the next two extremal examples of graphs having more than 2d-1 vertices.    Example 1. Let H be any graph on d vertices and let S be an independent set of vertices disjoint from H, \\(| S| \\geq d-1\\). Let G be the graph obtained by adding edges from every vertex of S to every vertex of H.    Example 2. Let H be the disjoint union of complete graphs each having d-2 vertices. Let x, z, v be three vertices disjoint from H and let F be any graph with \\(V(F)=\\{x,v,z\\}\\). Let G be the graph obtained by joining every vertex of H to every vertex of F.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106857$A80EB730-C746-4ECA-8D7A-6FD5A76A79EB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ebe4d44a08a58073803722e37fc039de15c45af0","datavalue":{"value":{"entity-type":"item","numeric-id":761465,"id":"Q761465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106857$235860D7-80BE-4BDE-8BA2-9934FD2EF06A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106857$936CDC6B-9ED1-4B8C-8507-8C5E73FEA28C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106857$49CC9FA7-4D15-4F9E-AA20-131CCAF0BB26","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e4783231b8ce491e4ec13569828359bcfddfdfd5","datavalue":{"value":"4063121","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106857$36101D97-E3D0-4F19-AFF0-F4053546013A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"33c7da59d74a91b71afe9af245bbb143dcad1b84","datavalue":{"value":"2-connected graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106857$10FE137B-04DA-4E37-92AE-B36E2AC47339","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3ebc22d8187ea672fec2c0fc855212abe29ca422","datavalue":{"value":"longest path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106857$E163F59C-FE73-453A-A50A-73844F64B6A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106857$4CF720B4-9945-4A41-B0A4-81C3A6805366","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5e0748da353cbaca68136c5462da6bce39666c","datavalue":{"value":"3-connected graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106857$F25CE77D-53BE-4C05-80FC-7CD8DF3A100E","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":"Q1106857$0B8D110F-01CA-4356-9EB3-A904CCA0820E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"efa5229264b561ad025a487908d9f59a41282cdd","datavalue":{"value":{"entity-type":"item","numeric-id":3703921,"id":"Q3703921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106857$0516007B-A2A4-4801-8C03-A9D5CAA65C00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106857$7946121D-7BF3-4AD1-AD48-50E2EDC9DEDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"845a14593f6dcdadd637a81f9b6ce69d6d230a40","datavalue":{"value":{"entity-type":"item","numeric-id":3333075,"id":"Q3333075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106857$91D3BFA6-A865-4D7C-BCA5-77587206A8D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85929f3453c0a582170aeac93c5defaef03b7501","datavalue":{"value":{"entity-type":"item","numeric-id":1065022,"id":"Q1065022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106857$4A9E93F4-6679-49A4-8239-F36316C8DF95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cdd1b8395bb1a08f6f4a613b0e1d9db42613abc1","datavalue":{"value":{"entity-type":"item","numeric-id":1167743,"id":"Q1167743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106857$70E0599F-36A8-48F5-99D1-76525C46510C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac0ec4868dba1b37d1adb8bb9f6a23d6c0a862f5","datavalue":{"value":{"entity-type":"item","numeric-id":3880849,"id":"Q3880849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106857$F626B8DD-9118-4685-ADA8-CEC75D38CEE8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1f475beb07bec2b5ef9f5d25abcfa9ddabfcc200","datavalue":{"value":"https://doi.org/10.1016/0012-365x(88)90117-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1106857$BF6786B5-F2BB-4D88-9D6A-269091D8F119","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2c71187ca33996984f86ccbf6c756753e84b0849","datavalue":{"value":"W2019516099","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106857$7CEB3D1B-BC6F-4310-B2CC-2B9AD1FC0EC6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9e86e179451e65532516893b4580dc429c8469f","datavalue":{"value":{"entity-type":"item","numeric-id":5897109,"id":"Q5897109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e20b15c2326855b042e0c2838148b10a75410d6f","datavalue":{"value":{"amount":"+0.820371150970459","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":"Q1106857$33276BB5-D486-4638-8A9A-96B7BE587E18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0066327753252f5762ef297bc62c25f495f43c0c","datavalue":{"value":{"entity-type":"item","numeric-id":2715999,"id":"Q2715999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"17275e8321e0f3944f137692cf71d0e34e5dd383","datavalue":{"value":{"amount":"+0.7942873239517212","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":"Q1106857$9BDE0C27-A3DF-46B4-972B-84C0940C14F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cbdb98cde4b6f145f881a46c366d09bf639e066e","datavalue":{"value":{"entity-type":"item","numeric-id":1379162,"id":"Q1379162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a5a9059518e2b9a31e2619bdcc81ed81736a500","datavalue":{"value":{"amount":"+0.776529848575592","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":"Q1106857$AE6CF378-3AAF-48A5-824B-4D2ACF102650","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ddfb2987992d3a59dede3c437d981745e74f193","datavalue":{"value":{"entity-type":"item","numeric-id":1180435,"id":"Q1180435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cdd8cac5eb70fffe0ace68d7295a65e43eec3903","datavalue":{"value":{"amount":"+0.7721929550170898","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":"Q1106857$0748F9C4-1E82-4229-8348-D1295ED18137","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c2f5d8de8b9e52b0767b164210b37c9ccd16c12c","datavalue":{"value":{"entity-type":"item","numeric-id":2746207,"id":"Q2746207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be60816e2d6bf82d5187c08d436797d077b86da9","datavalue":{"value":{"amount":"+0.7677711844444275","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":"Q1106857$CAEA07EA-C002-4241-8291-937F5FE0E14B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Extremal 3-connected graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Extremal_3-connected_graphs"}}}}}