Theory Graph_Theory_Relations

section ‹Graph Theory Inheritance›
text ‹ This theory aims to demonstrate the use of locales to transfer theorems between different 
graph/combinatorial structure representations ›

theory Graph_Theory_Relations imports Undirected_Graph_Basics Bipartite_Graphs 
"Design_Theory.Block_Designs" "Design_Theory.Group_Divisible_Designs"

subsection ‹ Design Inheritance ›
text ‹A graph is a type of incidence system, and more specifically a type of combinatorial design. 
This section demonstrates the correspondence between designs and graphs ›

sublocale graph_system  inc: incidence_system V "mset_set E"
  by (unfold_locales) (metis wellformed elem_mset_set ex_in_conv infinite_set_mset_mset_set) 

sublocale fin_graph_system  finc: finite_incidence_system V "mset_set E"
  using finV by unfold_locales

sublocale fin_ulgraph  d: design V "mset_set E"
  using edge_size empty_not_edge fin_edges by unfold_locales auto 

sublocale fin_ulgraph  d: simple_design V "mset_set E"
  by unfold_locales (simp add: fin_edges) 

locale graph_has_edges = graph_system + 
  assumes edges_nempty: "E  {}"

locale fin_sgraph_wedges = fin_sgraph + graph_has_edges

text ‹The simple graph definition of degree overlaps with the definition of a point replication number ›
sublocale fin_sgraph_wedges  bd: block_design V "mset_set E" 2
  rewrites "point_replication_number (mset_set E) x = degree x" 
    and "points_index (mset_set E) vs = degree_set vs"
proof (unfold_locales) 
  show "inc.𝖻  0"  by (simp add: edges_nempty fin_edges)
  show "bl. bl ∈# mset_set E  card bl = 2" by (simp add: fin_edges two_edges)
  show "mset_set E index vs = degree_set vs"
    unfolding degree_set_def points_index_def by (simp add: fin_edges) 
  have "size {#b ∈# (mset_set E) . x  b#} = card (incident_edges x)"
    unfolding incident_edges_def vincident_def
    by (simp add: fin_edges) 
  then show "mset_set E rep x = degree x" using alt_degree_def point_replication_number_def
    by metis

locale fin_bipartite_graph_wedges = fin_bipartite_graph + fin_sgraph_wedges

sublocale fin_bipartite_graph_wedges  group_design V "mset_set E" "{X, Y}"
  by unfold_locales (simp_all add: partition ne)

subsection ‹Adjacency Relation Definition ›

text ‹ Another common formal representation of graphs is as a vertex set and an adjacency relation
This is a useful representation in some contexts - we use locales to enable the transfer of 
results between the two representations, specifically the mutual sublocales approach ›

locale graph_rel = 
  fixes vertices :: "'a set" ("V")
  fixes adj_rel :: "'a rel"
  assumes wf: " u v. (u, v)  adj_rel  u  V  v  V"

abbreviation "adj u v  (u, v)  adj_rel"

lemma wf_alt: "adj u v  (u, v)  V × V"
  using wf by blast


locale ulgraph_rel = graph_rel + 
  assumes sym_adj: "sym adj_rel"

text ‹ This definition makes sense in the context of an undirected graph ›
definition edge_set:: "'a edge set" where
"edge_set  {{u, v} | u v. adj u v}"

lemma obtain_edge_pair_adj:
  assumes "e  edge_set"
  obtains u v where "e = {u, v}" and "adj u v" 
  using assms edge_set_def mem_Collect_eq
  by fastforce 

lemma adj_to_edge_set_card: 
  assumes "e  edge_set"
  shows "card e = 1  card e = 2"
proof -
  obtain u v where "e = {u, v}" and "adj u v" using obtain_edge_pair_adj assms by blast 
  then show ?thesis by (cases "u = v", simp_all)

lemma adj_to_edge_set_card_lim: 
  assumes "e  edge_set"
  shows "card e > 0  card e  2"
proof -
  obtain u v where "e = {u, v}" and "adj u v" using obtain_edge_pair_adj assms by blast 
  then show ?thesis by (cases "u = v", simp_all)

lemma edge_set_wf: "e  edge_set  e  V"
  using obtain_edge_pair_adj wf by (metis insert_iff singletonD subsetI) 

lemma is_graph_system: "graph_system V edge_set"
  by (unfold_locales) (simp add: edge_set_wf)

lemma sym_alt: "adj u v  adj v u"
  using sym_adj by (meson symE)

lemma is_ulgraph: "ulgraph V edge_set"
  using ulgraph_axioms_def is_graph_system adj_to_edge_set_card_lim 
  by (intro_locales) auto


context ulgraph

definition adj_relation :: "'a rel" where
"adj_relation  {(u, v) | u v . vert_adj u v}"

lemma adj_relation_wf: "(u, v)  adj_relation  {u, v}  V"
  unfolding adj_relation_def using vert_adj_imp_inV by auto

lemma adj_relation_sym: "sym adj_relation"
  unfolding adj_relation_def sym_def using vert_adj_sym by auto

lemma is_ulgraph_rel: "ulgraph_rel V adj_relation"
  using adj_relation_wf adj_relation_sym by (unfold_locales) auto

text ‹ Temporary interpretation - mutual sublocale setup ›

interpretation ulgraph_rel V adj_relation by (rule is_ulgraph_rel)

lemma vert_adj_rel_iff: 
  assumes "u  V" "v  V"
  shows "vert_adj u v  adj u v"
  using adj_relation_def by auto

lemma edges_rel_is: "E = edge_set"
proof -
  have "E = {{u, v} | u v . vert_adj u v}"
  proof (intro subset_antisym subsetI)
    show "x. x  {{u, v} |u v. vert_adj u v}  x  E"
      using vert_adj_def by fastforce
    fix x assume "x  E"
    then have "x  V" and "card x > 0" and "card x  2" using wellformed edge_size by auto 
    then obtain u v where "x = {u, v}" and "{u, v}  E"
      by (metis x  E alt_edge_size card_1_singletonE card_2_iff insert_absorb2) 
    then show "x  {{u, v} |u v. vert_adj u v}" unfolding vert_adj_def by blast    
  then have "E = {{u, v} | u v . adj u v}" using vert_adj_rel_iff Collect_cong
    by (smt (verit) vert_adj_imp_inV) 
  thus ?thesis using edge_set_def by simp


context ulgraph_rel 

text ‹ Temporary interpretation - mutual sublocale setup ›
interpretation ulgraph V edge_set by (rule is_ulgraph)

lemma rel_vert_adj_iff:  "vert_adj u v  adj u v"
proof (intro iffI)
  assume "vert_adj u v"
  then have "{u, v}  edge_set" by (simp add: vert_adj_def)
  then show "adj u v" using edge_set_def
    by (metis (no_types, lifting) doubleton_eq_iff obtain_edge_pair_adj sym_alt) 
  assume "adj u v"
  then have "{u, v}  edge_set" using edge_set_def by auto
  then show "vert_adj u v" by (simp add: vert_adj_def)

lemma rel_item_is: "(u, v)  adj_rel  (u, v)  adj_relation"
  unfolding adj_relation_def using rel_vert_adj_iff by auto

lemma rel_edges_is: "adj_rel = adj_relation"
  using rel_item_is by auto


sublocale ulgraph_rel  ulgraph "V" "edge_set"
  rewrites "ulgraph.adj_relation edge_set = adj_rel"
  using local.is_ulgraph rel_edges_is by simp_all

sublocale ulgraph  ulgraph_rel "V" "adj_relation"
  rewrites "ulgraph_rel.edge_set adj_relation = E"
  using is_ulgraph_rel edges_rel_is by simp_all

locale sgraph_rel = ulgraph_rel +
  assumes irrefl_adj: "irrefl adj_rel"

lemma irrefl_alt: "adj u v  u  v"
  using irrefl_adj irrefl_def by fastforce 

lemma edge_is_card2: 
  assumes "e  edge_set"
  shows "card e = 2"
proof -
  obtain u v where eq: "e = {u, v}" and "adj u v" using assms edge_set_def by blast
  then have "u  v" using irrefl_alt by simp
  thus ?thesis using eq by simp

lemma is_sgraph: "sgraph V edge_set"
  using is_graph_system edge_is_card2 sgraph_axioms_def by (intro_locales) auto


context sgraph

lemma is_rel_irrefl_alt: 
  assumes "(u, v)  adj_relation"
  shows "u  v"
proof -
  have "vert_adj u v" using adj_relation_def assms by blast
  then have "{u, v}  E" using vert_adj_def by simp
  then have "card {u, v} = 2" using two_edges by simp
  thus ?thesis by auto

lemma is_rel_irrefl: "irrefl adj_relation"
  using irrefl_def is_rel_irrefl_alt by auto

lemma is_sgraph_rel: "sgraph_rel V adj_relation"
  by (unfold_locales) (simp add: is_rel_irrefl)


sublocale sgraph_rel  sgraph V "edge_set"
  rewrites "ulgraph.adj_relation edge_set = adj_rel"
  using is_sgraph rel_edges_is by simp_all

sublocale sgraph  sgraph_rel V "adj_relation"
  rewrites "ulgraph_rel.edge_set adj_relation = E"
  using is_sgraph_rel edges_rel_is by simp_all