#OK to post
#Yuxuan Yang, April 3rd, Assignment 19

with(combinat):

#2.BestEdge(G)：tries to pick an "optimal edge" for CrP
#My idea is the edge with max degree sum.
BestEdge:=proc(G) local deg,n,degsum,m,j,k,e:
n:=nops(G[1]):
m:=nops(G[2]):
deg:=[0$n]:
degsum:=[0$m]:
for e in G[2] do
 for k from 1 to n do
  if G[1][k] in e then
   deg[k]:=deg[k]+1:
  fi:
 od:
od:

for j from 1 to m do
 for k from 1 to n do
  if G[1][k] in G[2][j] then
   degsum[j]:=degsum[j]+deg[k]:
  fi:
 od:
od:

G[2][max[index](degsum)]:
end:


#3
#P:=CrP([{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, {{1, 2}, {1, 5}, {1, 6}, {2, 3}, {2, 9}, {3, 4}, {3, 7}, {4, 5}, {4, 10}, {5, 8}, {6, 7}, {6, 10}, {7, 8}, {8, 9}, {9, 10}}], t)
#subs(t=1000,P)
#985104546350143270697605296000

#Checking it by Maple:
#with(GraphTheory):with(SpecialGraphs):
#subs(t=1000,ChromaticPolynomial(PetersenGraph(), t))
#985104546350143270697605296000






















#START k-Coloroing
#DelEd(G,e): Delets the edge e
DelEd:=proc(G,e) :

if not member(e,G[2]) then
 RETURN(FAIL):
fi:

[G[1],G[2] minus {e}]:
end:

#Contracts the edge e in the graph G, identifying its two members
ConEd:=proc(G,e) local i,j:


if not member(e,G[2]) then
 RETURN(FAIL):
fi:

i:=min(e):
j:=max(e):

[subs(j=i,G[1]), subs(j=i,G[2]) minus {{i}}]:


end:


#CrP(G,t): The Chromatic polynomial of the graph G in the variable t

CrP:=proc(G,t)  local e:

if G[2]={} then
 RETURN(t^nops(G[1])):
else
e:=G[2][1]:
CrP(DelEd(G,e),t)-CrP(ConEd(G,e),t):
fi:

end: