diff options
Diffstat (limited to 'graph-checker/src/theorems/forbidden.rs')
| -rw-r--r-- | graph-checker/src/theorems/forbidden.rs | 66 |
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])); +} |