# Graph Theory, Sage, LaTeX

LaTeX and Graphs

Simple, clean, and good control over the basics. The "Normal" look with labels outside the vertex:

Set the thickness of the line creating the vertex and the line that is used as an edge

\renewcommand*{\VertexLineWidth}{1pt}%vertex thickness24
\renewcommand*{\EdgeLineWidth}{1pt}% edge thickness

Set the specifics of vertex R1 inside options

LabelOut for a label outside. Without this, the default is to put the label inside the vertex.

LPos sets the position of the label. With 0 representing a label to the right of the vertex, 90 representing above the vertex, 180 to the left of the vertex and 270 under the vertex. By choosing a number between 0 and 360 you have excellent control over the label.

L=$v_1$   will set the label to what you want.

\Vertex[LabelOut,Lpos=270,L=$v_1$,x=0,y=0]{R1}

Labels inside the vertices:

More Graph Details

There are lots of options to change the look of the graph. Many of these options are set after entering the tikzpicture environment. Changes can be made later by appending information to the Vertex or Edge style:
\SetVertexNormal[Shape=circle,LineWidth = 2pt,FillColor = orange!60]
\tikzset{VertexStyle/.append style ={minimum size = 25pt, outer sep = 0pt,text=purple}}
\SetUpEdge[lw=1.2pt]
\tikzset{EdgeStyle/.append style = {color = blue!60}}

Labels can be added to particular edges as needed. This produces the edge labelled "5":

\Edge[label=$5$,labelstyle = {draw,text=red}](R2)(R3)

The look of a single edge can be adjusted by changing the edge through the scope environment. This part of the code produces the fat red edge:

\begin{scope}[EdgeStyle/.append style = {color = red!90,line width=4pt}]
\Edge (R5)(R7)
\end{scope}

The Altermundus contributions tkz-graph package and the tkz-berge packages, (designed by Alain Mathes) provides the graph theoretic capabilities of LaTeX. The documentation of tkz-graph, in French, can be found on CTAN here. The tkz-berge package CTAN documentation, in French, is here.

SageTex and Graph Theory

Determining the exact position for vertices in Petersen's graph or any large graph would take too much time to set the positions individually. That's where Sage's knowledge of graph theory can be utilized with SageTex.

1. The LaTeX options for graph theory using Sage are here.
2. Documentation for undirected graph parameters are here.
3. Named graphs known to Sage are here.

From the third link I'm going to create the Paley graph.

Looking at some parts of the code:

H=graphs.PaleyGraph(17)
H.set_pos(H.layout_circular()) #arrange the vertices in a circle
H.set_latex_options(scale=3.5,graphic_size=(3,3))
Chi = H.chromatic_number(algorithm="DLX")
Beta = H.independent_set()

The first line selects the graph, and the second line chooses one possible method for placing the vertices. The 4th and 5th line calculate parameters for the specific graph. 've found that setting the graph options using the first link isn't always effective but by relying on the Altermundus packages for graphs you can achieve what you want.

\GraphInit[vstyle=Normal]
\SetVertexNormal[Shape=circle,LineWidth = 1pt]
\tikzset{EdgeStyle/.append style = {color = blue!60, line width=1pt}}
\sage{H}

Sage will take care of the rest. By combining the Altermundus packages with SageTex, creating graphs is relatively simple. Moreover, Sage will calculate the graph parameters which makes mistakes less likely.

Changing the labels

If you use Sage to generate graphs you'll find there are times when the vertices aren't labelled the way you expect them or want them to be:

In this case the graph is the line graph of a complete graph on 5 vertices, so labelling the vertices with 2-tuples makes sense--the vertex (0,2) would correspond to the edge (in K_5) from vertex 0 to vertex 2. but the "None" part of each label is annoying, to say the least. And that has created an additional problem of vertices which are too big. Luckily Sage has the ability to relabel vertices. In this case, I'm going to relabel using the vertices as just 2-tuples corresponding to vertices in K_5 of {1,2,3,4,5} to get:

The relevant part of the code is

g = graphs.CompleteGraph(m)
H= g.line_graph().complement()
H.relabel([(i,j) for i in range(1,m+1) for j in range(i+1,m+1)])

The first line creates the complete graph on m, equal to 5, vertices. The second line uses Sage's knowledge of graphs to create the line graph of K_5. The line

H.relabel([(i,j) for i in range(1,m+1) for j in range(i+1,m+1)])

generates the desired labels and as a result the vertices are not so huge. The code for the figure above can be downloaded here: RelabelGraph  (.tex)