From 3b4759951c3d8f03166da1d26b37ba02b0e066f2 Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin.drew@gmail.com>
Date: Wed, 17 May 2023 12:27:32 +0400
Subject: Added theory for forbidden subgraphs

---
 graph-checker/src/theorems/forbidden.rs | 66 +++++++++++++++++++++++++++++++++
 1 file changed, 66 insertions(+)

(limited to 'graph-checker/src/theorems/forbidden.rs')

diff --git a/graph-checker/src/theorems/forbidden.rs b/graph-checker/src/theorems/forbidden.rs
index 8c70916..9450b07 100644
--- a/graph-checker/src/theorems/forbidden.rs
+++ b/graph-checker/src/theorems/forbidden.rs
@@ -226,3 +226,69 @@ pub fn conjecture17(g: &Graph) -> bool {
 
     return g.is_4_connected() && g.is_free_of(&vec![claw]);
 }
+
+pub fn theorem_all_2con(g: &Graph) -> bool {
+    let claw = Graph {
+        size: 4,
+        matrix: vec![
+            vec![0, 1, 1, 1],
+            vec![1, 0, 0, 0],
+            vec![1, 0, 0, 0],
+            vec![1, 0, 0, 0],
+        ],
+    };
+
+    let ng = Graph {
+        size: 6,
+        matrix: vec![
+            vec![0, 1, 1, 1, 0, 0],
+            vec![1, 0, 1, 0, 0, 1],
+            vec![1, 1, 0, 0, 1, 0],
+            vec![1, 0, 0, 0, 0, 0],
+            vec![0, 0, 1, 0, 0, 0],
+            vec![0, 1, 0, 0, 0, 0],
+        ],
+    };
+
+    let p6 = Graph {
+        size: 6,
+        matrix: vec![
+            vec![0, 1, 0, 0, 0, 0],
+            vec![1, 0, 1, 0, 0, 0],
+            vec![0, 1, 0, 1, 0, 0],
+            vec![0, 0, 1, 0, 1, 0],
+            vec![0, 0, 0, 1, 0, 1],
+            vec![0, 0, 0, 0, 1, 0],
+        ],
+    };
+
+    let z2 = Graph {
+        size: 5,
+        matrix: vec![
+            vec![0, 1, 0, 0, 0],
+            vec![1, 0, 1, 0, 0],
+            vec![0, 1, 0, 1, 1],
+            vec![0, 0, 1, 0, 1],
+            vec![0, 0, 1, 1, 1],
+        ],
+    };
+
+    let wg = Graph {
+        size: 6,
+        matrix: vec![
+            vec![0, 1, 1, 0, 0, 0],
+            vec![1, 0, 1, 0, 1, 0],
+            vec![1, 1, 0, 1, 0, 0],
+            vec![0, 0, 1, 0, 0, 0],
+            vec![0, 1, 0, 0, 0, 1],
+            vec![0, 0, 0, 0, 1, 0],
+        ],
+    };
+
+    return g.is_2_connected()
+        && g.is_free_of(&vec![claw])
+        && (g.is_free_of(&vec![ng])
+            || g.is_free_of(&vec![p6])
+            || g.is_free_of(&vec![z2])
+            || g.is_free_of(&vec![wg]));
+}
-- 
cgit v1.2.3