# part A: brute force TP from the definitions; 2026-10-17 06:59
# random tree T6 parents: [None, 0, 0, 1, 1, 0]
{'name': 'P5', 'n': 5, 'median': True, 'bipartite': True, 'n_convex': 15, 'convex_enum_matches_subset_bruteforce': True, 'lemma1_count_prod_subtrees': (15, 15, True), 'lemma1_every_convex_is_box_of_subtrees': True, 'lemma2_each_step_one_factor_one_vertex': True, 'theta_transitive': True, 'n_hyperplanes': 4, 'tested': 650, 'mismatch_TP_vs_2hyp': 0, 'mismatch_TP_empty_vs_2d': 0, 'violations_TP_le_2TS': 0, 'max_TP_over_TS': 2.0, 'first_mismatch': None}
{'name': 'K1,3', 'n': 4, 'median': True, 'bipartite': True, 'n_convex': 11, 'convex_enum_matches_subset_bruteforce': True, 'lemma1_count_prod_subtrees': (11, 11, True), 'lemma1_every_convex_is_box_of_subtrees': True, 'lemma2_each_step_one_factor_one_vertex': True, 'theta_transitive': True, 'n_hyperplanes': 3, 'tested': 240, 'mismatch_TP_vs_2hyp': 0, 'mismatch_TP_empty_vs_2d': 0, 'violations_TP_le_2TS': 0, 'max_TP_over_TS': 2.0, 'first_mismatch': None}
{'name': 'spider(2,1,1)', 'n': 5, 'median': True, 'bipartite': True, 'n_convex': 17, 'convex_enum_matches_subset_bruteforce': True, 'lemma1_count_prod_subtrees': (17, 17, True), 'lemma1_every_convex_is_box_of_subtrees': True, 'lemma2_each_step_one_factor_one_vertex': True, 'theta_transitive': True, 'n_hyperplanes': 4, 'tested': 650, 'mismatch_TP_vs_2hyp': 0, 'mismatch_TP_empty_vs_2d': 0, 'violations_TP_le_2TS': 0, 'max_TP_over_TS': 2.0, 'first_mismatch': None}
{'name': 'randtree6[0, 0, 1, 1, 0]', 'n': 6, 'median': True, 'bipartite': True, 'n_convex': 28, 'convex_enum_matches_subset_bruteforce': True, 'lemma1_count_prod_subtrees': (28, 28, True), 'lemma1_every_convex_is_box_of_subtrees': True, 'lemma2_each_step_one_factor_one_vertex': True, 'theta_transitive': True, 'n_hyperplanes': 5, 'tested': 1512, 'mismatch_TP_vs_2hyp': 0, 'mismatch_TP_empty_vs_2d': 0, 'violations_TP_le_2TS': 0, 'max_TP_over_TS': 2.0, 'first_mismatch': None}
{'name': '(P2)x(P2)', 'n': 4, 'median': True, 'bipartite': True, 'n_convex': 9, 'convex_enum_matches_subset_bruteforce': True, 'lemma1_count_prod_subtrees': (9, 9, True), 'lemma1_every_convex_is_box_of_subtrees': True, 'lemma2_each_step_one_factor_one_vertex': True, 'theta_transitive': True, 'n_hyperplanes': 2, 'tested': 240, 'mismatch_TP_vs_2hyp': 0, 'mismatch_TP_empty_vs_2d': 0, 'violations_TP_le_2TS': 0, 'max_TP_over_TS': 2.0, 'first_mismatch': None}
{'name': '(P3)x(P3)', 'n': 9, 'median': True, 'bipartite': True, 'n_convex': 36, 'convex_enum_matches_subset_bruteforce': True, 'lemma1_count_prod_subtrees': (36, 36, True), 'lemma1_every_convex_is_box_of_subtrees': True, 'lemma2_each_step_one_factor_one_vertex': True, 'theta_transitive': True, 'n_hyperplanes': 4, 'tested': 26730, 'mismatch_TP_vs_2hyp': 0, 'mismatch_TP_empty_vs_2d': 0, 'violations_TP_le_2TS': 0, 'max_TP_over_TS': 2.0, 'first_mismatch': None}
{'name': '(P4)x(P3)', 'n': 12, 'median': True, 'bipartite': True, 'n_convex': 60, 'convex_enum_matches_subset_bruteforce': True, 'lemma1_count_prod_subtrees': (60, 60, True), 'lemma1_every_convex_is_box_of_subtrees': True, 'lemma2_each_step_one_factor_one_vertex': True, 'theta_transitive': True, 'n_hyperplanes': 5, 'tested': 71856, 'mismatch_TP_vs_2hyp': 0, 'mismatch_TP_empty_vs_2d': 0, 'violations_TP_le_2TS': 0, 'max_TP_over_TS': 2.0, 'first_mismatch': None}
{'name': '(K1,3)x(P3)', 'n': 12, 'median': True, 'bipartite': True, 'n_convex': 66, 'convex_enum_matches_subset_bruteforce': True, 'lemma1_count_prod_subtrees': (66, 66, True), 'lemma1_every_convex_is_box_of_subtrees': True, 'lemma2_each_step_one_factor_one_vertex': True, 'theta_transitive': True, 'n_hyperplanes': 5, 'tested': 71856, 'mismatch_TP_vs_2hyp': 0, 'mismatch_TP_empty_vs_2d': 0, 'violations_TP_le_2TS': 0, 'max_TP_over_TS': 2.0, 'first_mismatch': None}
{'name': '(K1,3)x(K1,3)', 'n': 16, 'median': True, 'bipartite': True, 'n_convex': 121, 'convex_enum_matches_subset_bruteforce': True, 'lemma1_count_prod_subtrees': (121, 121, True), 'lemma1_every_convex_is_box_of_subtrees': True, 'lemma2_each_step_one_factor_one_vertex': True, 'theta_transitive': True, 'n_hyperplanes': 6, 'tested': 111872, 'mismatch_TP_vs_2hyp': 0, 'mismatch_TP_empty_vs_2d': 0, 'violations_TP_le_2TS': 0, 'max_TP_over_TS': 2.0, 'first_mismatch': None}
{'name': '(spider(2,1,1))x(P2)', 'n': 10, 'median': True, 'bipartite': True, 'n_convex': 51, 'convex_enum_matches_subset_bruteforce': True, 'lemma1_count_prod_subtrees': (51, 51, True), 'lemma1_every_convex_is_box_of_subtrees': True, 'lemma2_each_step_one_factor_one_vertex': True, 'theta_transitive': True, 'n_hyperplanes': 5, 'tested': 37600, 'mismatch_TP_vs_2hyp': 0, 'mismatch_TP_empty_vs_2d': 0, 'violations_TP_le_2TS': 0, 'max_TP_over_TS': 2.0, 'first_mismatch': None}
{'name': '((P2)x(P2))x(P2)', 'n': 8, 'median': True, 'bipartite': True, 'n_convex': 27, 'convex_enum_matches_subset_bruteforce': True, 'lemma1_count_prod_subtrees': (27, 27, True), 'lemma1_every_convex_is_box_of_subtrees': True, 'lemma2_each_step_one_factor_one_vertex': True, 'theta_transitive': True, 'n_hyperplanes': 3, 'tested': 12352, 'mismatch_TP_vs_2hyp': 0, 'mismatch_TP_empty_vs_2d': 0, 'violations_TP_le_2TS': 0, 'max_TP_over_TS': 2.0, 'first_mismatch': None}
{'name': '((P3)x(P3))x(P2)', 'n': 18, 'median': True, 'bipartite': True, 'n_convex': 108, 'lemma1_count_prod_subtrees': (108, 108, True), 'lemma1_every_convex_is_box_of_subtrees': True, 'lemma2_each_step_one_factor_one_vertex': True, 'theta_transitive': True, 'n_hyperplanes': 5, 'tested': 120528, 'mismatch_TP_vs_2hyp': 0, 'mismatch_TP_empty_vs_2d': 0, 'violations_TP_le_2TS': 0, 'max_TP_over_TS': 2.0, 'first_mismatch': None}
{'name': '(randtree6[0, 0, 1, 1, 0])x(P3)', 'n': 18, 'median': True, 'bipartite': True, 'n_convex': 168, 'lemma1_count_prod_subtrees': (168, 168, True), 'lemma1_every_convex_is_box_of_subtrees': True, 'lemma2_each_step_one_factor_one_vertex': True, 'theta_transitive': True, 'n_hyperplanes': 7, 'tested': 120528, 'mismatch_TP_vs_2hyp': 0, 'mismatch_TP_empty_vs_2d': 0, 'violations_TP_le_2TS': 0, 'max_TP_over_TS': 2.0, 'first_mismatch': None}
{'name': '(P5)x(P4)', 'n': 20, 'median': True, 'bipartite': True, 'n_convex': 150, 'lemma1_count_prod_subtrees': (150, 150, True), 'lemma1_every_convex_is_box_of_subtrees': True, 'lemma2_each_step_one_factor_one_vertex': True, 'theta_transitive': True, 'n_hyperplanes': 7, 'tested': 144400, 'mismatch_TP_vs_2hyp': 0, 'mismatch_TP_empty_vs_2d': 0, 'violations_TP_le_2TS': 0, 'max_TP_over_TS': 2.0, 'first_mismatch': None}
{'name': '((K1,3)x(P2))x(P2)', 'n': 16, 'median': True, 'bipartite': True, 'n_convex': 99, 'convex_enum_matches_subset_bruteforce': True, 'lemma1_count_prod_subtrees': (99, 99, True), 'lemma1_every_convex_is_box_of_subtrees': True, 'lemma2_each_step_one_factor_one_vertex': True, 'theta_transitive': True, 'n_hyperplanes': 5, 'tested': 73472, 'mismatch_TP_vs_2hyp': 0, 'mismatch_TP_empty_vs_2d': 0, 'violations_TP_le_2TS': 0, 'max_TP_over_TS': 2.0, 'first_mismatch': None}
# non-product median graphs
{'name': 'grid3x3-[(2, 2)]', 'n': 8, 'median': True, 'bipartite': True, 'n_convex': 31, 'convex_enum_matches_subset_bruteforce': True, 'theta_transitive': True, 'n_hyperplanes': 4, 'tested': 12352, 'mismatch_TP_vs_2hyp': 0, 'mismatch_TP_empty_vs_2d': 0, 'violations_TP_le_2TS': 0, 'max_TP_over_TS': 2.0, 'first_mismatch': None}
{'name': 'two squares sharing a vertex', 'n': 7, 'median': True, 'bipartite': True, 'n_convex': 26, 'convex_enum_matches_subset_bruteforce': True, 'theta_transitive': True, 'n_hyperplanes': 4, 'tested': 8036, 'mismatch_TP_vs_2hyp': 0, 'mismatch_TP_empty_vs_2d': 0, 'violations_TP_le_2TS': 0, 'max_TP_over_TS': 2.0, 'first_mismatch': None}
{'name': '5-wheel of squares', 'n': 11, 'median': True, 'bipartite': True, 'n_convex': 57, 'convex_enum_matches_subset_bruteforce': True, 'theta_transitive': True, 'n_hyperplanes': 5, 'tested': 20207, 'mismatch_TP_vs_2hyp': 0, 'mismatch_TP_empty_vs_2d': 0, 'violations_TP_le_2TS': 0, 'max_TP_over_TS': 2.0, 'first_mismatch': None}
{'name': 'Q3 + square glued on an edge', 'n': 10, 'median': True, 'bipartite': True, 'n_convex': 42, 'convex_enum_matches_subset_bruteforce': True, 'theta_transitive': True, 'n_hyperplanes': 4, 'tested': 27600, 'mismatch_TP_vs_2hyp': 0, 'mismatch_TP_empty_vs_2d': 0, 'violations_TP_le_2TS': 0, 'max_TP_over_TS': 2.0, 'first_mismatch': None}
{'name': '2x3 grid + pendant path of length 2', 'n': 8, 'median': True, 'bipartite': True, 'n_convex': 33, 'convex_enum_matches_subset_bruteforce': True, 'theta_transitive': True, 'n_hyperplanes': 5, 'tested': 12352, 'mismatch_TP_vs_2hyp': 0, 'mismatch_TP_empty_vs_2d': 0, 'violations_TP_le_2TS': 0, 'max_TP_over_TS': 2.0, 'first_mismatch': None}
# negative controls (non-median graphs): median test must fail; formula need not hold
{'name': 'C6', 'n': 6, 'median': False, 'bipartite': True, 'n_convex': 19, 'convex_enum_matches_subset_bruteforce': True, 'theta_transitive': True, 'n_hyperplanes': 3, 'tested': 792, 'mismatch_TP_vs_2hyp': 0, 'mismatch_TP_empty_vs_2d': 0, 'violations_TP_le_2TS': 0, 'max_TP_over_TS': 2.0, 'first_mismatch': None}
{'name': 'K2,3', 'n': 5, 'median': False, 'bipartite': True, 'n_convex': 12, 'convex_enum_matches_subset_bruteforce': True, 'theta_transitive': False, 'n_hyperplanes': 1, 'tested': 400, 'mismatch_TP_vs_2hyp': 354, 'mismatch_TP_empty_vs_2d': 0, 'violations_TP_le_2TS': 0, 'max_TP_over_TS': 2.0, 'first_mismatch': (0, (), 1, 4, 2)}
{'name': 'C5', 'n': 5, 'median': False, 'bipartite': False, 'n_convex': 16, 'convex_enum_matches_subset_bruteforce': True, 'theta_transitive': False, 'n_hyperplanes': 1, 'tested': 400, 'mismatch_TP_vs_2hyp': 378, 'mismatch_TP_empty_vs_2d': 0, 'violations_TP_le_2TS': 0, 'max_TP_over_TS': 2.0, 'first_mismatch': (0, (), 2, 4, 2)}
{'name': 'Q3 minus a vertex', 'n': 7, 'median': False, 'bipartite': True, 'n_convex': 23, 'convex_enum_matches_subset_bruteforce': True, 'theta_transitive': True, 'n_hyperplanes': 3, 'tested': 1421, 'mismatch_TP_vs_2hyp': 0, 'mismatch_TP_empty_vs_2d': 0, 'violations_TP_le_2TS': 0, 'max_TP_over_TS': 2.0, 'first_mismatch': None}
# negative controls on P3xP3 (must be detected)
NC0 correct setup, formula 2*hyp: (0, 3726)
NC1 formula 2*hyp+1 (must mismatch): (3726, 3726)
NC2 formula hyp (must mismatch): (3708, 3726)
NC3 wrong hull (no closure) (must mismatch): (588, 3726)
NC4 boundary reading 'any' (must mismatch): (3558, 3726); max TP(x,{},y) = 2 (diam = 4)
NC4 boundary reading 'dist2' (must mismatch): (3558, 3726); max TP(x,{},y) = 4 (diam = 4)
NC5 Held-Karp TS vs permutation brute force: mismatches 0/11520; corrupted TS mismatches 9678/11520 (must be > 0)
# done in 14.6 s
