Added theory for forbidden subgraphs

1 files changed, 66 insertions, 0 deletions

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]));
+}