{"entities":{"Q1900184":{"pageid":1910926,"ns":120,"title":"Item:Q1900184","lastrevid":73722468,"modified":"2026-04-14T17:02:24Z","type":"item","id":"Q1900184","labels":{"en":{"language":"en","value":"Non-contractible edges in a 3-connected graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 806476"}},"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":"Q1900184$2C6400AE-ED9D-4E5C-AC25-5AEC231BD9D5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e434837247afdefc75c5b2dd7d281c4437a88050","datavalue":{"value":{"text":"Non-contractible edges in a 3-connected graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1900184$D0BBCBA8-EE3B-4AD1-940A-9FEB938F4F81","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"771ce205d6f7650cec1538f4dc02b85cec0ac889","datavalue":{"value":"0835.05035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1900184$333CA18B-A694-4139-9B53-41E13A9EB6FB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ae6dd1b965ae02f849f8fa419f2104ebf761adad","datavalue":{"value":"10.1007/BF01299741","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1900184$8439C5F9-3E58-4388-967C-0A8126F5C5BA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a670df13e76d03f298849c21819158785379e5e5","datavalue":{"value":{"entity-type":"item","numeric-id":234310,"id":"Q234310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900184$2A7BA497-4885-4B9B-9465-713267210A43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a57de2e11ea0a7c1b4e027ef0d1354f56003f3b7","datavalue":{"value":{"entity-type":"item","numeric-id":214980,"id":"Q214980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900184$D002D3AA-04A9-4AD1-8147-557F0C35C308","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ea3cb9fe6240a14735eacdd3f47c5ce6de5321a8","datavalue":{"value":{"entity-type":"item","numeric-id":214981,"id":"Q214981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900184$D465FB24-96C0-4953-B488-0BD76D86BC9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"acf4d8e2d67e9424baeed386dae60d5abe642819","datavalue":{"value":{"entity-type":"item","numeric-id":251549,"id":"Q251549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900184$D7DD5D2E-1FDD-4C83-8BC2-42823E3A5B1E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900184$36194EF6-0F6D-41A4-820F-EDADF7662CDF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7292501a0480bc9e4358f9782541b0bd9309e5eb","datavalue":{"value":{"time":"+1995-10-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1900184$8444EB5F-9938-4459-B6C0-23B7A8277E97","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0038397f5bfa47c1086faf6e5961b16aa6234e9b","datavalue":{"value":"Given a simple finite graph \\(G\\) and an edge \\(e\\) of \\(G\\), denote by \\(Ge\\) the graph obtained by identifying the two vertices incident with \\(e\\) and deleting any resulting loops and multiple edges. If \\(G\\) is 3-connected but \\(Ge\\) is not 3-connected, then \\(e\\) is said to be non-contractable. It is shown that if \\(G\\) is a 3-connected graph on \\(p > 4\\) vertices then the number of non-contractible edges of \\(G\\) is at most \\(3p - \\lfloor 3 (\\sqrt {24p + 25} - 5)/2 \\rfloor\\). While this result is best possible in the sense that there exist arbitrarily large graphs that attain this bound, it is claimed (proof omitted because of its length) that the slightly sharper upper bound of \\(\\lfloor 3 [p - (\\sqrt {24p + 25} - 5)/2] \\rfloor\\) is also valid.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1900184$85886544-90ED-44E5-9649-FD89AA64FA63","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2420d8bcf60fc74d0291a3c59f694629f273e260","datavalue":{"value":{"entity-type":"item","numeric-id":426905,"id":"Q426905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900184$2FC23EC1-D175-490F-9382-DC127DF0215C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1900184$2F6E17B4-5A44-49CF-95E0-68432FD67983","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1900184$2A8EACDA-AD92-45F8-B5BA-7C778D8CE9C3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2ed9cef55fea733d21e6c9559ea3c119eb93f674","datavalue":{"value":"806476","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1900184$F2A4753E-319C-4853-96F0-5B737A140ABD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4605262f950382e87dc58df46038532164191769","datavalue":{"value":"contraction","type":"string"},"datatype":"string"},"type":"statement","id":"Q1900184$0B9459BD-1102-46AA-A1EA-E38DF8873063","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"abab6d51bc0722532b523ea42f8eaf8ed745f963","datavalue":{"value":"cut","type":"string"},"datatype":"string"},"type":"statement","id":"Q1900184$F89AB661-A754-44AE-A368-9BE105CD8149","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eba61a8abead030333429495c832d733d94064bd","datavalue":{"value":"connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1900184$1C0430A4-CB5B-40C2-BA28-E28A9C387EA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f053a97fb62befa7ec7e2c1b97b05888c445d28b","datavalue":{"value":"non-contractible edges","type":"string"},"datatype":"string"},"type":"statement","id":"Q1900184$E96053C2-EB1B-4A55-B3E3-929904741979","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b6906d309434fd0c76118d23a6a15594e9c5ca39","datavalue":{"value":"bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1900184$09F12CA8-30ED-42B4-AE18-97C6C69BE10B","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":"Q1900184$4845EF7C-7C25-4241-B9AD-7EEF47A7F750","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc90b7f6c4f8510a2652b6c2ba1a93bb32f42c9d","datavalue":{"value":{"entity-type":"item","numeric-id":4277986,"id":"Q4277986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900184$60D70BF1-E26E-411F-BAA0-917AEAD798BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb0ebc121be9815f124187315b4c55653ba304ac","datavalue":{"value":{"entity-type":"item","numeric-id":1087557,"id":"Q1087557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900184$79740CEB-D9AF-46DA-8C7A-1432AAA07D7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"caeb18590387fa9d3b1bc28484b50886f95d046d","datavalue":{"value":{"entity-type":"item","numeric-id":1197021,"id":"Q1197021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900184$79996A52-F5A4-497E-A334-FD36488EA9DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af271e2570d011cc0706a1f7748813e556954b75","datavalue":{"value":{"entity-type":"item","numeric-id":3801577,"id":"Q3801577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900184$0FF919E0-0963-41A6-9F04-E6BD429EA510","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f41d49e608d5ffc8abc77bd4e4e561119c3c473e","datavalue":{"value":{"entity-type":"item","numeric-id":1142781,"id":"Q1142781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900184$0572CAEB-FC88-4830-95DC-6481DB7F2E33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"babde1bf2e0a2ade6f34d07684713bf5358637f4","datavalue":{"value":{"entity-type":"item","numeric-id":3284374,"id":"Q3284374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900184$45010AD3-5179-4913-BAB8-E2A982534027","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"182709f709ad5dc4c261461d752eced1a5b83ff2","datavalue":{"value":{"entity-type":"item","numeric-id":913818,"id":"Q913818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900184$799EE1C9-B130-4BC7-92F6-2F300A7B1906","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c8ac530ac09d274363ff5c27fa2ae216cd281713","datavalue":{"value":{"entity-type":"item","numeric-id":4818462,"id":"Q4818462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d42e90edbd7587971276039557a960ec1a267dd","datavalue":{"value":{"amount":"+0.9446373581886292","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":"Q1900184$3836D63E-464C-412D-8635-BA7BA76ACE2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e9ddeffb627afab4d17bc90e5efc8ae32cc2ea7","datavalue":{"value":{"entity-type":"item","numeric-id":2287736,"id":"Q2287736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6cca4724e270f7cb62371eb4312e32e18ca9bc02","datavalue":{"value":{"amount":"+0.8832215666770935","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":"Q1900184$BB061DEA-99B2-4BEF-9235-2C9EB384F8C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c2b3757ab8ecdc1590eebd4ce4d7c0c66bd3908","datavalue":{"value":{"entity-type":"item","numeric-id":1111571,"id":"Q1111571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a65c39b7d9ee861961b6ca0afe71ed7d2cb5e83","datavalue":{"value":{"amount":"+0.8825250267982483","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":"Q1900184$C2ADBFAF-9A9E-4C84-BAD6-3C6103061DAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f85011c9578f76d4f85928676bb6cb302d60ca8b","datavalue":{"value":{"entity-type":"item","numeric-id":1087557,"id":"Q1087557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4afc32c5ae99e23fc5e5d3cf33abfac084007ae3","datavalue":{"value":{"amount":"+0.8723061680793762","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":"Q1900184$C2EF9291-867E-41A7-B15C-9A06A88C3E54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"996d5a87633645e45cc19f201f3b3d4e8b7339a1","datavalue":{"value":{"entity-type":"item","numeric-id":3351386,"id":"Q3351386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b7af4e1772e03808a16924d2842fb633e84beb34","datavalue":{"value":{"amount":"+0.8669554591178894","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":"Q1900184$731024D8-7DC1-4D62-9BB3-50237BC15439","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Non-contractible edges in a 3-connected graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Non-contractible_edges_in_a_3-connected_graph"}}}}}