Added theorems from Gould 2003

1 files changed, 201 insertions, 0 deletions

diff --git a/graph-checker/src/theorems/forbidden.rs b/graph-checker/src/theorems/forbidden.rs
index 615cdb1..8c70916 100644
--- a/graph-checker/src/theorems/forbidden.rs
+++ b/graph-checker/src/theorems/forbidden.rs
@@ -25,3 +25,204 @@ pub fn theorem3_1(g: &Graph) -> bool {
 
     return g.is_2_connected() && g.is_free_of(&forbidden);
 }
+
+pub fn theorem3_2(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 forbidden = vec![claw];
+    return g.size >= 3
+        && g.is_connected()
+        && g.is_locally_connected()
+        && g.is_free_of(&forbidden);
+}
+
+pub fn corollary3_5(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 ig = Graph {
+        size: 4,
+        matrix: vec![
+            vec![0, 1, 0, 0],
+            vec![1, 0, 1, 0],
+            vec![0, 1, 0, 1],
+            vec![0, 0, 1, 0],
+        ],
+    };
+
+    let ag = Graph {
+        size: 5,
+        matrix: vec![
+            vec![0, 1, 1, 0, 0],
+            vec![1, 0, 0, 1, 0],
+            vec![1, 0, 0, 0, 1],
+            vec![0, 1, 0, 0, 0],
+            vec![0, 0, 1, 0, 0],
+        ],
+    };
+
+    let is_2 = g.is_2_connected();
+    let claw_free = g.is_free_of(&vec![claw]);
+    return (is_2 && claw_free && g.is_free_of(&vec![ig]))
+        || (is_2 && claw_free && g.is_free_of(&vec![ag]));
+}
+
+// 2003 Gould
+
+pub fn theorem85(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],
+        ],
+    };
+
+    return g.is_2_connected() && g.is_free_of(&vec![claw, ng]);
+}
+
+pub fn theorem86(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 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],
+        ],
+    };
+
+    return g.is_2_connected() && g.is_free_of(&vec![claw, p6]);
+}
+
+pub fn theorem87(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 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],
+        ],
+    };
+
+    return g.is_2_connected() && g.is_free_of(&vec![claw, z2]);
+}
+
+pub fn theorem88(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 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, wg]);
+}
+
+pub fn theorem96(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],
+        ],
+    };
+
+    return g.is_3_connected() && g.is_free_of(&vec![claw, ng]);
+}
+
+pub fn conjecture17(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],
+        ],
+    };
+
+    return g.is_4_connected() && g.is_free_of(&vec![claw]);
+}