Restructured project into multiple files

7 files changed, 449 insertions, 432 deletions

diff --git a/graph-checker/Cargo.lock b/graph-checker/Cargo.lock
index 41ac3f5..4feb4c5 100644
--- a/graph-checker/Cargo.lock
+++ b/graph-checker/Cargo.lock
@@ -3,5 +3,5 @@
 version = 3
 
 [[package]]
-name = "coursework-year3"
+name = "graph-checker"
 version = "0.1.0"
diff --git a/graph-checker/rustfmt.toml b/graph-checker/rustfmt.toml
new file mode 100644
index 0000000..5cd3daa
--- /dev/null
+++ b/graph-checker/rustfmt.toml
@@ -0,0 +1,2 @@
+max_width = 80
+
diff --git a/graph-checker/src/graph.rs b/graph-checker/src/graph.rs
new file mode 100644
index 0000000..4c06660
--- /dev/null
+++ b/graph-checker/src/graph.rs
@@ -0,0 +1,276 @@
+use std::fmt;
+
+pub struct Graph {
+    pub size: usize,
+    pub matrix: Vec<Vec<i32>>,
+}
+
+pub struct Cutset {
+    pub cardinality: usize,
+    pub vertices: Vec<i32>,
+    pub graph: Graph,
+}
+
+impl Clone for Graph {
+    fn clone(&self) -> Self {
+        let mut matrix = vec![vec![0; self.size]; self.size];
+        for row in 0..self.size {
+            for col in 0..self.size {
+                matrix[row][col] = self.matrix[row][col];
+            }
+        }
+        return Graph {
+            size: self.size,
+            matrix,
+        };
+    }
+}
+
+impl fmt::Display for Graph {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        for row in 0..self.size {
+            for col in 0..self.size {
+                write!(f, "{}", self.matrix[row][col])?;
+                if col < self.size - 1 {
+                    write!(f, " ")?;
+                }
+            }
+            if row < self.size - 1 {
+                write!(f, "\n")?;
+            }
+        }
+        return Ok(());
+    }
+}
+
+fn iterate(n: usize) -> Vec<Vec<i32>> {
+    let mut components = Vec::new();
+
+    let mut v: Vec<i32> = vec![0; n];
+    loop {
+        let mut sum: usize = 0;
+        for i in &v {
+            sum += *i as usize;
+        }
+
+        if sum == v.len() {
+            break;
+        }
+
+        let mut k = 0;
+        for i in 0..v.len() {
+            if v[i] == 1 {
+                v[i] = 0;
+            } else {
+                k = i;
+                break;
+            }
+        }
+        v[k] = 1;
+        components.push(v.clone());
+    }
+
+    return components;
+}
+
+impl Graph {
+    pub fn from_g6(line: &String) -> Graph {
+        let mut chars: Vec<u8> = Vec::new();
+        for character in line.chars() {
+            chars.push((character as i32 - 63) as u8);
+        }
+        // TODO: spec allows multi-byte vector size
+        let size = chars[0] as usize;
+        let bytes = &chars[1..];
+
+        let mut matrix: Vec<Vec<i32>> = vec![vec![0; size]; size];
+        let mut i = 0;
+        for col in 1..size {
+            for row in 0..col {
+                let bit: i32 = (bytes[i / 6] >> (5 - i % 6) & 1) as i32;
+                matrix[row][col] = bit;
+                matrix[col][row] = bit;
+                i += 1;
+            }
+        }
+        return Graph { size, matrix };
+    }
+
+    pub fn degree(&self, vertex: usize) -> usize {
+        let mut sum: usize = 0;
+        for i in &self.matrix[vertex] {
+            sum += if *i == 0 { 0 } else { 1 } as usize;
+        }
+        return sum;
+    }
+
+    pub fn min_degree(&self) -> usize {
+        let mut min = self.size + 1;
+        for i in 0..self.size {
+            let d = self.degree(i);
+            if d < min {
+                min = d;
+            }
+        }
+        return min;
+    }
+
+    pub fn get_closure_traced(&self, trace_steps: bool) -> Graph {
+        let mut step = if trace_steps { 2 } else { 1 };
+
+        let mut closure = self.clone();
+        for _ in 0..(closure.size * closure.size) {
+            let mut changed = false;
+            for row in 0..closure.size {
+                for col in 0..closure.size {
+                    if row == col || closure.matrix[row][col] != 0 {
+                        continue;
+                    }
+                    let sum = closure.degree(row) + closure.degree(col);
+                    if sum >= closure.size {
+                        closure.matrix[row][col] = step;
+                        if trace_steps {
+                            step += 1;
+                        }
+                        changed = true;
+                    }
+                }
+            }
+            if !changed {
+                break;
+            }
+        }
+        return closure;
+    }
+
+    pub fn cutsets(&self) -> Vec<Cutset> {
+        let mut cs = Vec::new();
+        for vertices in iterate(self.size) {
+            let mut g = self.clone();
+            for vertex in 0..g.size {
+                for i in 0..g.size {
+                    if vertices[vertex] == 0 {
+                        g.matrix[vertex as usize][i as usize] = 0;
+                        g.matrix[i as usize][vertex as usize] = 0;
+                    }
+                }
+            }
+            let cardinality = vertices.iter().sum::<i32>() as usize;
+            cs.push(Cutset {
+                cardinality,
+                vertices: vertices.clone(),
+                graph: g,
+            });
+        }
+        return cs;
+    }
+
+    pub fn max_independent_cutset(&self) -> Cutset {
+        let mut max_cutset = None;
+        for cutset in self.cutsets() {
+            if cutset.graph.is_independent() {
+                match &max_cutset {
+                    None => max_cutset = Some(cutset),
+                    Some(m_cutset) => {
+                        if cutset.cardinality > m_cutset.cardinality {
+                            max_cutset = Some(cutset);
+                        }
+                    }
+                };
+            }
+        }
+        return max_cutset.unwrap();
+    }
+
+    fn dfs(&self, vertex: &usize, visited: &mut Vec<usize>) {
+        visited[*vertex] = 1;
+        for i in 0..self.size {
+            if visited[i] == 0 && self.matrix[*vertex][i] != 0 {
+                self.dfs(&i, visited);
+            }
+        }
+    }
+
+    fn count_components_partial(&self, included_vertices: &Vec<i32>) -> usize {
+        let mut visited = vec![0; self.size];
+        for i in 0..included_vertices.len() {
+            if included_vertices[i] == 0 {
+                visited[i] = 1;
+            }
+        }
+        let mut count = 0;
+        while visited.iter().sum::<usize>() != visited.len() {
+            let mut next = 0;
+            for i in 0..self.size {
+                if visited[i] == 0 {
+                    next = i;
+                    break;
+                }
+            }
+            self.dfs(&next, &mut visited);
+            count += 1;
+        }
+        return count;
+    }
+
+    pub fn count_components(&self) -> usize {
+        self.count_components_partial(&vec![1; self.size])
+    }
+
+    pub fn get_closure(&self) -> Graph {
+        self.get_closure_traced(false)
+    }
+
+    pub fn check_toughness(&self, t: f64) -> bool {
+        for cutset in self.cutsets() {
+            let components_count =
+                cutset.graph.count_components_partial(&cutset.vertices) as f64;
+            let cut_cardinality = (self.size - cutset.cardinality) as f64;
+            if components_count > 1.0 && cut_cardinality < t * components_count
+            {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    pub fn get_toughness(&self) -> f64 {
+        let mut left: f64 = 0.0;
+        let mut right: f64 = 1024.0; // Reasonable limit
+        let eps: f64 = 1e-9;
+
+        while (right - left).abs() > eps {
+            let mid = (left + right) / 2.0;
+
+            if self.check_toughness(mid) == false {
+                right = mid;
+            } else {
+                left = mid;
+            }
+        }
+
+        return (left * 1e7).round() / 1e7;
+    }
+
+    pub fn is_complete(&self) -> bool {
+        for row in 0..self.size {
+            for col in 0..self.size {
+                if row != col && self.matrix[row][col] == 0 {
+                    return false;
+                }
+            }
+        }
+        return true;
+    }
+
+    pub fn is_independent(&self) -> bool {
+        for row in 0..self.size {
+            for col in 0..self.size {
+                if row != col && self.matrix[row][col] != 0 {
+                    return false;
+                }
+            }
+        }
+        return true;
+    }
+}
diff --git a/graph-checker/src/main.rs b/graph-checker/src/main.rs
index e09d15f..54af780 100644
--- a/graph-checker/src/main.rs
+++ b/graph-checker/src/main.rs
@@ -1,359 +1,14 @@
-use std::fmt;
 use std::io::{self, BufRead};
 use std::time::Instant;
 
-struct Graph {
-    size: usize,
-    matrix: Vec<Vec<i32>>,
-}
-
-struct Cutset {
-    cardinality: usize,
-    vertices: Vec<i32>,
-    graph: Graph,
-}
-
-impl Clone for Graph {
-    fn clone(&self) -> Self {
-        let mut matrix = vec![vec![0; self.size]; self.size];
-        for row in 0..self.size {
-            for col in 0..self.size {
-                matrix[row][col] = self.matrix[row][col];
-            }
-        }
-        return Graph {
-            size: self.size,
-            matrix,
-        };
-    }
-}
-
-impl fmt::Display for Graph {
-    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        for row in 0..self.size {
-            for col in 0..self.size {
-                write!(f, "{}", self.matrix[row][col])?;
-                if col < self.size - 1 {
-                    write!(f, " ")?;
-                }
-            }
-            if row < self.size - 1 {
-                write!(f, "\n")?;
-            }
-        }
-        return Ok(());
-    }
-}
-
-fn iterate(n: usize) -> Vec<Vec<i32>> {
-    let mut components = Vec::new();
-
-    let mut v: Vec<i32> = vec![0; n];
-    loop {
-        let mut sum: usize = 0;
-        for i in &v {
-            sum += *i as usize;
-        }
-
-        if sum == v.len() {
-            break;
-        }
-
-        let mut k = 0;
-        for i in 0..v.len() {
-            if v[i] == 1 {
-                v[i] = 0;
-            } else {
-                k = i;
-                break;
-            }
-        }
-        v[k] = 1;
-        components.push(v.clone());
-    }
-
-    return components;
-}
-
-impl Graph {
-    fn from_g6(line: &String) -> Graph {
-        let mut chars: Vec<u8> = Vec::new();
-        for character in line.chars() {
-            chars.push((character as i32 - 63) as u8);
-        }
-        // TODO: spec allows multi-byte vector size
-        let size = chars[0] as usize;
-        let bytes = &chars[1..];
-
-        let mut matrix: Vec<Vec<i32>> = vec![vec![0; size]; size];
-        let mut i = 0;
-        for col in 1..size {
-            for row in 0..col {
-                let bit: i32 = (bytes[i / 6] >> (5 - i % 6) & 1) as i32;
-                matrix[row][col] = bit;
-                matrix[col][row] = bit;
-                i += 1;
-            }
-        }
-        return Graph { size, matrix };
-    }
-
-    fn degree(&self, vertex: usize) -> usize {
-        let mut sum: usize = 0;
-        for i in &self.matrix[vertex] {
-            sum += if *i == 0 { 0 } else { 1 } as usize;
-        }
-        return sum;
-    }
-
-    fn min_degree(&self) -> usize {
-        let mut min = self.size + 1;
-        for i in 0..self.size {
-            let d = self.degree(i);
-            if d < min {
-                min = d;
-            }
-        }
-        return min;
-    }
-
-    fn get_closure_traced(&self, trace_steps: bool) -> Graph {
-        let mut step = if trace_steps { 2 } else { 1 };
-
-        let mut closure = self.clone();
-        for _ in 0..(closure.size * closure.size) {
-            let mut changed = false;
-            for row in 0..closure.size {
-                for col in 0..closure.size {
-                    if row == col || closure.matrix[row][col] != 0 {
-                        continue;
-                    }
-                    let sum = closure.degree(row) + closure.degree(col);
-                    if sum >= closure.size {
-                        closure.matrix[row][col] = step;
-                        if trace_steps {
-                            step += 1;
-                        }
-                        changed = true;
-                    }
-                }
-            }
-            if !changed {
-                break;
-            }
-        }
-        return closure;
-    }
-
-    fn get_hamiltonian_cycle(&self) -> Vec<usize> {
-        let closure = self.get_closure_traced(true);
-
-        let mut cycle = Vec::new();
-        for i in 0..self.size - 1 {
-            cycle.push(i + 1);
-        }
-        cycle.push(0);
-
-        loop {
-            let mut start = 0;
-            let mut m = 0;
-
-            let mut end = start;
-            let mut new_start = start;
-            let mut current = start;
-            loop {
-                let next = cycle[current];
-                let val = closure.matrix[current][next];
-                // println!("{current} -> {next} = {val}");
-                if val > m {
-                    m = val;
-                    end = current;
-                    new_start = next;
-                }
-                current = next;
-                if current == start {
-                    break;
-                }
-            }
-            if m == 1 {
-                break;
-            }
-            // println!("New start: {new_start}, end: {end}, m = {m}");
-            start = new_start;
-
-            let mut s = start;
-            let mut current = cycle[start];
-            while current != end {
-                let next = cycle[current];
-                let u1 = closure.matrix[start][next];
-                let u2 = closure.matrix[end][current];
-                if u1 < m && u2 < m {
-                    s = current;
-                    break;
-                }
-                current = next;
-            }
-            // println!("s = {s}");
-
-            let mut new_cycle = Vec::new();
-            new_cycle.push(start);
-            let mut current = cycle[s];
-            while current != end {
-                new_cycle.push(current);
-                current = cycle[current];
-            }
-            new_cycle.push(end);
-            {
-                let mut tmp = Vec::new();
-                let mut current = cycle[start];
-                while current != s {
-                    tmp.push(current);
-                    current = cycle[current];
-                }
-                tmp.push(s);
-                tmp.reverse();
-                for i in tmp {
-                    new_cycle.push(i);
-                }
-            }
-            for i in 0..self.size - 1 {
-                cycle[new_cycle[i]] = new_cycle[i + 1];
-            }
-            cycle[new_cycle[self.size - 1]] = new_cycle[0];
-        }
-
-        return cycle;
-    }
+mod graph;
+use crate::graph::Graph;
 
-    fn cutsets(&self) -> Vec<Cutset> {
-        let mut cs = Vec::new();
-        for vertices in iterate(self.size) {
-            let mut g = self.clone();
-            for vertex in 0..g.size {
-                for i in 0..g.size {
-                    if vertices[vertex] == 0 {
-                        g.matrix[vertex as usize][i as usize] = 0;
-                        g.matrix[i as usize][vertex as usize] = 0;
-                    }
-                }
-            }
-            let cardinality = vertices.iter().sum::<i32>() as usize;
-            cs.push(Cutset {
-                cardinality,
-                vertices: vertices.clone(),
-                graph: g,
-            });
-        }
-        return cs;
-    }
-
-    fn max_independent_cutset(&self) -> Cutset {
-        let mut max_cutset = None;
-        for cutset in self.cutsets() {
-            if cutset.graph.is_independent() {
-                match &max_cutset {
-                    None => max_cutset = Some(cutset),
-                    Some(m_cutset) => {
-                        if cutset.cardinality > m_cutset.cardinality {
-                            max_cutset = Some(cutset);
-                        }
-                    }
-                };
-            }
-        }
-        return max_cutset.unwrap();
-    }
-
-    fn dfs(&self, vertex: &usize, visited: &mut Vec<usize>) {
-        visited[*vertex] = 1;
-        for i in 0..self.size {
-            if visited[i] == 0 && self.matrix[*vertex][i] != 0 {
-                self.dfs(&i, visited);
-            }
-        }
-    }
-
-    fn count_components_partial(&self, included_vertices: &Vec<i32>) -> usize {
-        let mut visited = vec![0; self.size];
-        for i in 0..included_vertices.len() {
-            if included_vertices[i] == 0 {
-                visited[i] = 1;
-            }
-        }
-        let mut count = 0;
-        while visited.iter().sum::<usize>() != visited.len() {
-            let mut next = 0;
-            for i in 0..self.size {
-                if visited[i] == 0 {
-                    next = i;
-                    break;
-                }
-            }
-            self.dfs(&next, &mut visited);
-            count += 1;
-        }
-        return count;
-    }
-
-    fn count_components(&self) -> usize {
-        self.count_components_partial(&vec![1; self.size])
-    }
-
-    fn get_closure(&self) -> Graph {
-        self.get_closure_traced(false)
-    }
-
-    fn check_toughness(&self, t: f64) -> bool {
-        for cutset in self.cutsets() {
-            let components_count = cutset.graph.count_components_partial(&cutset.vertices) as f64;
-            let cut_cardinality = (self.size - cutset.cardinality) as f64;
-            if components_count > 1.0 && cut_cardinality < t * components_count {
-                return false;
-            }
-        }
-        return true;
-    }
-
-    fn get_toughness(&self) -> f64 {
-        let mut left: f64 = 0.0;
-        let mut right: f64 = 1024.0; // Reasonable limit
-        let eps: f64 = 1e-9;
-
-        while (right - left).abs() > eps {
-            let mid = (left + right) / 2.0;
-
-            if self.check_toughness(mid) == false {
-                right = mid;
-            } else {
-                left = mid;
-            }
-        }
-
-        return (left * 1e7).round() / 1e7;
-    }
-
-    fn is_complete(&self) -> bool {
-        for row in 0..self.size {
-            for col in 0..self.size {
-                if row != col && self.matrix[row][col] == 0 {
-                    return false;
-                }
-            }
-        }
-        return true;
-    }
-
-    fn is_independent(&self) -> bool {
-        for row in 0..self.size {
-            for col in 0..self.size {
-                if row != col && self.matrix[row][col] != 0 {
-                    return false;
-                }
-            }
-        }
-        return true;
-    }
-}
+mod theorems;
+use crate::theorems::basic::{
+    bondy_chvatal_hamiltonian_cycle, dirac_theorem, ore_theorem, posa_theorem,
+};
+use crate::theorems::toughness::{theorem15, theorem25};
 
 struct Counters {
     graphs: i32,
@@ -383,84 +38,6 @@ impl Counters {
     }
 }
 
-fn theorem15(g: &Graph, toughness: f64, min_degree: f64) -> bool {
-    let max_ind_cutset_size = g.max_independent_cutset().cardinality as f64;
-    let third_of_size = g.size as f64 / 3.0;
-    let tmp = if third_of_size > max_ind_cutset_size - 1.0 {
-        third_of_size
-    } else {
-        max_ind_cutset_size - 1.0
-    };
-
-    return toughness >= 1.0 && min_degree >= tmp;
-}
-
-fn theorem25(g: &Graph, toughness: f64, min_degree: f64) -> bool {
-    return min_degree > g.size as f64 / (toughness + 1.0) - 1.0;
-}
-
-fn dirac_theorem(g: &Graph) -> bool {
-    for vertex in 0..g.size {
-        if (g.degree(vertex) as f64) < g.size as f64 / 2.0 {
-            return false;
-        }
-    }
-    return true;
-}
-
-fn ore_theorem(g: &Graph) -> bool {
-    for v1 in 0..g.size {
-        for v2 in 0..g.size {
-            if v1 == v2 || g.matrix[v1][v2] != 0 {
-                continue;
-            }
-            let d1 = g.degree(v1);
-            let d2 = g.degree(v2);
-            if d1 + d2 < g.size {
-                return false;
-            }
-        }
-    }
-    return true;
-}
-
-fn posa_theorem(g: &Graph) -> bool {
-    let mut degrees = Vec::new();
-    for v in 0..g.size {
-        degrees.push(g.degree(v));
-    }
-
-    let end = if g.size % 2 == 0 {
-        g.size / 2
-    } else {
-        (g.size - 1) / 2
-    };
-
-    for k in 1..end {
-        let mut cnt = 0;
-        for d in &degrees {
-            if *d <= k {
-                cnt += 1;
-            }
-        }
-        if cnt >= k {
-            return false;
-        }
-    }
-    if g.size % 2 != 0 {
-        let mut cnt = 0;
-        for d in &degrees {
-            if *d <= end {
-                cnt += 1;
-            }
-        }
-        if cnt > end {
-            return false;
-        }
-    }
-    return true;
-}
-
 fn main() {
     let stdin = io::stdin();
 
@@ -535,7 +112,7 @@ fn main() {
             println!("Included vertices: {:?}", cutset.vertices);
             println!("Cutset cardinality: {}", cutset.cardinality);
 
-            let cycle = g.get_hamiltonian_cycle();
+            let cycle = bondy_chvatal_hamiltonian_cycle(&g);
             print!("Hamiltonian cycle: ");
             let start = 0;
             let mut current = start;
diff --git a/graph-checker/src/theorems/basic.rs b/graph-checker/src/theorems/basic.rs
new file mode 100644
index 0000000..41d5221
--- /dev/null
+++ b/graph-checker/src/theorems/basic.rs
@@ -0,0 +1,143 @@
+use crate::Graph;
+
+pub fn dirac_theorem(g: &Graph) -> bool {
+    for vertex in 0..g.size {
+        if (g.degree(vertex) as f64) < g.size as f64 / 2.0 {
+            return false;
+        }
+    }
+    return true;
+}
+
+pub fn ore_theorem(g: &Graph) -> bool {
+    for v1 in 0..g.size {
+        for v2 in 0..g.size {
+            if v1 == v2 || g.matrix[v1][v2] != 0 {
+                continue;
+            }
+            let d1 = g.degree(v1);
+            let d2 = g.degree(v2);
+            if d1 + d2 < g.size {
+                return false;
+            }
+        }
+    }
+    return true;
+}
+
+pub fn posa_theorem(g: &Graph) -> bool {
+    let mut degrees = Vec::new();
+    for v in 0..g.size {
+        degrees.push(g.degree(v));
+    }
+
+    let end = if g.size % 2 == 0 {
+        g.size / 2
+    } else {
+        (g.size - 1) / 2
+    };
+
+    for k in 1..end {
+        let mut cnt = 0;
+        for d in &degrees {
+            if *d <= k {
+                cnt += 1;
+            }
+        }
+        if cnt >= k {
+            return false;
+        }
+    }
+    if g.size % 2 != 0 {
+        let mut cnt = 0;
+        for d in &degrees {
+            if *d <= end {
+                cnt += 1;
+            }
+        }
+        if cnt > end {
+            return false;
+        }
+    }
+    return true;
+}
+
+pub fn bondy_chvatal_hamiltonian_cycle(graph: &Graph) -> Vec<usize> {
+    let closure = graph.get_closure_traced(true);
+
+    let mut cycle = Vec::new();
+    for i in 0..graph.size - 1 {
+        cycle.push(i + 1);
+    }
+    cycle.push(0);
+
+    loop {
+        let mut start = 0;
+        let mut m = 0;
+
+        let mut end = start;
+        let mut new_start = start;
+        let mut current = start;
+        loop {
+            let next = cycle[current];
+            let val = closure.matrix[current][next];
+            // println!("{current} -> {next} = {val}");
+            if val > m {
+                m = val;
+                end = current;
+                new_start = next;
+            }
+            current = next;
+            if current == start {
+                break;
+            }
+        }
+        if m == 1 {
+            break;
+        }
+        // println!("New start: {new_start}, end: {end}, m = {m}");
+        start = new_start;
+
+        let mut s = start;
+        let mut current = cycle[start];
+        while current != end {
+            let next = cycle[current];
+            let u1 = closure.matrix[start][next];
+            let u2 = closure.matrix[end][current];
+            if u1 < m && u2 < m {
+                s = current;
+                break;
+            }
+            current = next;
+        }
+        // println!("s = {s}");
+
+        let mut new_cycle = Vec::new();
+        new_cycle.push(start);
+        let mut current = cycle[s];
+        while current != end {
+            new_cycle.push(current);
+            current = cycle[current];
+        }
+        new_cycle.push(end);
+        {
+            let mut tmp = Vec::new();
+            let mut current = cycle[start];
+            while current != s {
+                tmp.push(current);
+                current = cycle[current];
+            }
+            tmp.push(s);
+            tmp.reverse();
+            for i in tmp {
+                new_cycle.push(i);
+            }
+        }
+        for i in 0..graph.size - 1 {
+            cycle[new_cycle[i]] = new_cycle[i + 1];
+        }
+        cycle[new_cycle[graph.size - 1]] = new_cycle[0];
+    }
+
+    return cycle;
+}
diff --git a/graph-checker/src/theorems/mod.rs b/graph-checker/src/theorems/mod.rs
new file mode 100644
index 0000000..2737cbd
--- /dev/null
+++ b/graph-checker/src/theorems/mod.rs
@@ -0,0 +1,2 @@
+pub mod basic;
+pub mod toughness;
diff --git a/graph-checker/src/theorems/toughness.rs b/graph-checker/src/theorems/toughness.rs
new file mode 100644
index 0000000..e659901
--- /dev/null
+++ b/graph-checker/src/theorems/toughness.rs
@@ -0,0 +1,17 @@
+use crate::Graph;
+
+pub fn theorem15(g: &Graph, toughness: f64, min_degree: f64) -> bool {
+    let max_ind_cutset_size = g.max_independent_cutset().cardinality as f64;
+    let third_of_size = g.size as f64 / 3.0;
+    let tmp = if third_of_size > max_ind_cutset_size - 1.0 {
+        third_of_size
+    } else {
+        max_ind_cutset_size - 1.0
+    };
+
+    return toughness >= 1.0 && min_degree >= tmp;
+}
+
+pub fn theorem25(g: &Graph, toughness: f64, min_degree: f64) -> bool {
+    return min_degree > g.size as f64 / (toughness + 1.0) - 1.0;
+}