New results on word-representable graphs
A graph $G=(V,E)$ is word-representable if there exists a word $w$ over the alphabet $V$ such that letters $x$ and $y$ alternate in $w$ if and only if $(x,y)\in E$ for each $x\neq y$. The set of word-representable graphs generalizes several important and well-studied graph families, such as circle graphs, comparability graphs, 3-colorable graphs, graphs of vertex degree at most 3, etc. By answering an open question from \cite{HalKitPya2}, in the present paper we show that not all graphs of vertex degree at most 4 are word-representable. Combining this result with some previously known facts, we derive that the number of $n$-vertex word-representable graphs is $2^{\frac{n^2}{3}+o(n^2)}$.
wrgr.tex
\documentclass[11pt]{article}
%\documentclass{article}
\usepackage[english]{babel}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}

%\pagestyle{empty} 
\addtolength{\topmargin}{-15mm}
\setlength{\textheight}{245mm}
\setlength{\textwidth}{145mm}

\usepackage{graphics,graphicx} % Packages to allow inclusion of graphics

\usepackage{latexsym}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
%\usepackage{eepic,epic}
\frenchspacing
\usepackage{graphicx}
\usepackage[hmargin=2.3cm,vmargin=2.5cm]{geometry}

\usepackage{tikz}
\usetikzlibrary{decorations.pathreplacing,arrows,automata}

\tikzstyle{vertex}=[circle,fill=black!100,text=white,inner sep=0.8mm]
\tikzstyle{point}=[circle,fill=black,inner sep=0.1mm]





\DeclareMathOperator{\asc}{\mathrm{asc}}

\setlength{\unitlength}{4mm}
\newcommand\p{\circle*{0.2}}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{conjecture}{Conjecture}
\newtheorem{corollary}{Corollary}

\date{}

\title{New results on word-representable graphs}
\author{Andrew Collins\thanks{Mathematics Institute, University of Warwick, Coventry, CV4 7AL, UK. 
Email: A.Collins.2@warwick.ac.uk.} 
\and 
Sergey Kitaev\thanks{Department of Computer and Information Sciences, University of Strathclyde, Glasgow, G1 1XH, UK. Email: sergey.kitaev@cis.strath.ac.uk}
\and 
Vadim V. Lozin\thanks{Mathematics Institute and DIMAP, University of Warwick, Coventry, CV4 7AL, UK. 
Email: V.Lozin@warwick.ac.uk.}}

\begin{document}

\maketitle
\thispagestyle{empty}

\begin{abstract} A graph $G=(V,E)$ is word-representable if there exists a word
$w$ over the alphabet $V$ such that letters $x$ and $y$ alternate in $w$ if and 
only if $(x,y)\in E$ for each $x\neq y$. The set of word-representable graphs
generalizes several important and well-studied graph families, such as 
circle graphs, comparability graphs, 3-colorable graphs, graphs of vertex degree 
at most 3, etc. By answering an open question from \cite{HalKitPya2}, in the present 
paper we show that not all graphs of vertex degree at most 4 are word-representable.
Combining this result with some previously known facts, we derive that the number of 
$n$-vertex word-representable graphs is  $2^{\frac{n^2}{3}+o(n^2)}$.
\end{abstract}

{\it Keywords}: Semi-transitive orientation; Hereditary property of graphs; Speed of hereditary properties 


\section{Introduction}
Let $G=(V,E)$ be a simple (i.e. undirected, without loops and multiple edges) graph
with vertex set $V$ and edge set $E$. We say $G$ is {\it word-representable} if there exists 
a word $w$ over the alphabet $V$ such that letters $x$ and $y$ alternate in $w$ if and 
only if $(x,y)\in E$ for each $x\neq y$. 

The notion of word-representable graphs has its roots in the study of the celebrated Perkins semigroup \cite{KitSei,S}.
These graphs possess many attractive properties (e.g. a maximum clique in such graphs can be found in polynomial time), 
and they provide a common generalization of several important graph families,  
such as circle graphs, comparability graphs, 3-colorable graphs, graphs of vertex degree 
at most 3 (see \cite{classes} for definitions of these families). 

Recently, a number of fundamental results on word-representable graphs were obtained 
in the literature \cite{HalKitPya1,HalKitPya2,KitPya,KitSalSevUlf1,KitSalSevUlf2}. In particular, 
Halld\'orsson et al. \cite{HalKitPya2} have shown that a graph is word-representable if and only 
if it admits a {\em semi-transitive orientation}. 
However, our knowledge on these graphs is still very limited and many important questions remain open. For example,
how hard is it to decide whether a given graph is 
word-representable or not? What is the minimum length of a word that represents a given graph?
How many word-representable graphs on $n$ vertices are there? Does this family include all graphs
of vertex degree at most 4? 

The last question was originally asked in \cite{HalKitPya2}. In the present paper we answer this question 
negatively by exhibiting a graph of vertex degree at most 4 which is not word-representable. 
This result allows us to obtain an upper bound on the asymptotic growth of the number of
$n$-vertex word-representable graphs. Combining this result with a lower bound that follows from some previously known
facts, we conclude that the number of $n$-vertex word-representable graphs is $2^{\frac{n^2}{3}+o(n^2)}$.   


All preliminary information related to the notion of word-representable graphs can be found in Section~\ref{sec:pre}.
In Section~\ref{sec:deg4}, we prove our negative result about graphs of degree at most 4 and in Section~\ref{sec:main}, 
we derive the asymptotic formula on the number of word-representable graphs. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Word-representable graphs: definition, examples and related results}
\label{sec:pre}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Distinct letters $x$ and $y$  {\em alternate} in a word $w$ if the deletion of all other letters
from the word results in either $xyxy\cdots$ or $yxyx\cdots$. 
A graph $G=(V,E)$ is \emph{word-representable} if there exists a word
$w$ over the alphabet $V$ such that letters $x$ and $y$ alternate in
$w$ if and only if $(x,y)\in E$ for each $x\neq y$. For example, 
the graph $M$ in Figure \ref{fig:representable-graphs} is word-representable, 
because the word $w=1213423$ has the right alternating properties, 
i.e. the only non-alternating pairs in this word are 1,3 and 1,4 that 
correspond to the only non-adjacent pairs of vertices in the graph. 

If a graph is word-representable, then there are infinitely many words representing it. 
For instance,  the complete graph $K_4$ in Figure \ref{fig:representable-graphs} can be represented by words
1234, 3142, 123412, 12341234, 432143214321, etc. In general, to represent a complete graph on $n$ vertices, 
one can start with writing up any permutation of length $n$ and adjoining from either side any number of copies 
of this permutation.  

\begin{figure}[ht]
\begin{center}
\includegraphics[scale=0.7]{representable-graphs.pdf}
\end{center}
\vspace{-20pt}
\caption{Three word-representable graphs $M$ (left), the complete graph $K_4$ (middle), and the Petersen graph (right)}
\label{fig:representable-graphs}
\end{figure}

If each letter appears exactly $k$ times in a word representing a graph, the graph is said to be \emph{$k$-word-representable}. 
It is known \cite{KitPya} that any word-representable graph is $k$-word-representable for some $k$. 
For example, a $3$-representation of the Petersen graph shown in Figure \ref{fig:representable-graphs} 
is $$1387296(10)7493541283(10)7685(10)194562.$$
It is not difficult to see that a graph is 1-representable if and only if it is complete.
Also, with a bit of work one can show that a graph is 2-representable if and only if it is a circle graph,
i.e. the intersection graph of chords in a circle. Thus, word-representable graphs generalize both complete graphs and circle graphs.
They also generalize two other important graph families, comparability graphs and 3-colorable graphs.
This can be shown through the notion of semi-transitive orientation. 

A directed graph (digraph) $G=(V,E)$ is \emph{semi-transitive} if it has no directed cycles
and for any directed path $v_1v_2\cdots v_k$ with $k\geq 4$ and $v_i\in V$, 
either $v_1v_k\not\in E$ or $v_iv_j\in E$ for all $1\le i<j\le k$. 
In the second case, when $v_1v_k\in E$, we say that $v_1v_k$ is a shortcut. 
The importance of this notion is due to the following result proved in \cite{HalKitPya2}.

\begin{theorem}[\cite{HalKitPya2}]\label{thm:semi-trans}  
A graph is word-representable if and only if it admits a semi-transitive orientation. 
\end{theorem}

From this theorem and the definition of semi-transitivity it follows
that all comparability (i.e. transitively orientable) graphs are word-representable.
Moreover, the theorem implies two more important corollaries. 

\begin{theorem}[\cite{HalKitPya2}]\label{thm:3col} 
All $3$-colorable graphs are word-representable.
\end{theorem}

\begin{proof} 
Partitioning a 3-colorable graph in three independent sets, say I, II and III, 
and orienting all edges in the graph so that they are oriented from I to II and III, and from II to III, 
we obtain a semi-transitive orientation.
\end{proof}


\begin{theorem}[\cite{HalKitPya2}]\label{thm:3deg} 
All graphs of vertex degree at most $3$ are word-representable.
\end{theorem}

\begin{proof} 
By Brooks' Theorem, every connected graph of vertex degree at most 3, except for the complete graph $K_4$, 
is 3-colorable, and hence word-representable by Theorem~\ref{thm:3col}. 
Also, as we observed earlier, all complete graphs are word-representable. Therefore, all connected graphs of degree 
at most 3 and hence all graphs of degree at most 3 are word-representable.
\end{proof}

Whether all graphs of degree at most 4 are word-representable is a natural question following from Theorem~\ref{thm:3deg},
which was originally asked in \cite{HalKitPya2}.  In the next section, we settle this question negatively.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{A non-representable graph of vertex degree at most 4}
\label{sec:deg4}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The main result of this section is that the graph $A$ represented in Figure~\ref{fig:A} is not word-representable.
To prove this, we will show that this graph does not admit a semi-transitive orientation. 
\begin{figure}[ht]
\begin{center}
	\begin{tikzpicture}
  		[scale=1,auto=left]
		
		
		\node[vertex] (n1) at (0,0)   { };
		\node[vertex] (n2) at (0,1)   { };
		\node[vertex] (n3) at (-1.5,2)   { };
		\node[vertex] (n4) at (-0.5,2)   { };
		\node[vertex] (n5) at (0.5,2)   { };
		\node[vertex] (n6) at (1.5,2)   { };
		\node[vertex] (n7) at (0,3)   { };		

			
		\foreach \from/\to in {n1/n2, n1/n3, n1/n6, n2/n4, n2/n5, n7/n3, n7/n4, n7/n5, n7/n6, n3/n4, n4/n5, n5/n6}
    	\draw (\from) -- (\to);
		
    	
%		\coordinate [label=center:$A$] (1) at (0,-0.5);
%		\coordinate [label=center:Figure $1$.] (1) at (0,-1.5);
	\end{tikzpicture}
\end{center}
\caption{The graph $A$}
\label{fig:A}
\end{figure}

\noindent
Our proof is a case analysis and the following lemma will be used frequently in the proof. 

\begin {lemma}\label{lem:1}
Let $D$ be a $K_4$-free graph admitting a semi-transitive orientation. 
Then no cycle of length $4$ in this orientation has three  consecutively oriented edges. 
\end{lemma}

\begin{proof}
If a semi-transitive orientation of $D$ contains a cycle of length four with three consecutively oriented edges,
then the fourth edge has to be oriented in the opposite direction to avoid an oriented cycle. 
However, the fourth edge now creates a shortcut. Hence the cycle must contain both chords to make it transitive, 
which is impossible because $D$ is $K_4$-free.
\end{proof}



\begin{theorem}\label{thm:A}
The graph $A$ does not admit a semi-transitive orientation.
\end{theorem}


\begin{proof} 
In order to prove that $A$ does not admit a semi-transitive orientation, we will explore {\it all} orientations 
of this graph and will show that each choice leads to a contradiction. At each step of the proof we choose 
a vertex and split the analysis into two cases depending on the orientation of the chosen edge. 
The chosen edge and its orientation will be shown by a solid arrow 
(\begin{tikzpicture} \draw [-latex] (0,0.1) -- (0.5,0.1); \draw [-] [white] (0,0) -- (0.01,0); \end{tikzpicture}). 
This choice of orientation may lead to other edges having an orientation assigned to them to satisfy Lemma~\ref{lem:1}. 
The orientations forced by the solid arrow through an application of  Lemma~\ref{lem:1} will be shown by means of double
arrows (\begin{tikzpicture} \draw [->>] (0,0.1) -- (0.5,0.1); \draw [-] [white] (0,0) -- (0.01,0); \end{tikzpicture}).
When we use Lemma~\ref{lem:1} to derive a double arrow, we always apply it with respect to a particular cycle of length 4. 
This cycle will be indicated by four white vertices. Since the graph $A$ has many cycles of length 4, repeated use 
of Lemma~\ref{lem:1} applied to different cycles may lead to a contradiction, where one more cycle of length 4 
has three consecutively oriented edges. We will show that in all possible cases a contradiction of this type arises. 
The proof is illustrated by diagrams.


\medskip
\noindent
{\it Case} 1: We start by choosing the orientation for the edge indicated in the diagram below.

\begin{center}
	\begin{tikzpicture}
  		[scale=1,auto=left]
		
		
		\node[vertex] (n1) at (0,0)   { };
		\node[vertex] (n2) at (0,1)   { };
		\node[vertex] (n3) at (-1.5,2)   { };
		\node[vertex] (n4) at (-0.5,2)   { };
		\node[vertex] (n5) at (0.5,2)   { };
		\node[vertex] (n6) at (1.5,2)   { };
		\node[vertex] (n7) at (0,3)   { };		

		\draw [-latex] (n1) -- (0,0.5);
		\draw (0,0.5) -- (n2);	
		

		\foreach \from/\to in {n1/n3, n1/n6, n2/n4, n2/n5, n7/n3, n7/n4, n7/n5, n7/n6, n3/n4, n4/n5, n5/n6}
    	\draw (\from) -- (\to);
		
    	
		
					
	\end{tikzpicture}

\end{center}

\medskip
\noindent
{\it Case} 1.1: Now we orient one more edge (solid arrow), which leads to two more orientations being assigned due to Lemma 1
(double arrows).

\begin{center}
	\begin{tikzpicture}
  		[scale=1,auto=left]
		
		\draw [->]  (n1) -- (0,0.5);
		\draw (0,0.5) -- (n2);
		\draw [-latex] (n6) -- (0.75,1);
		\draw (0.75,1) -- (n1);
		\draw [->>] (n6) -- (1,2);
		\draw (1,2) -- (n5);
		\draw [->>] (n5) -- (0.25,1.5);
		\draw (0.25,1.5) -- (n2);

		\node[vertex, fill=white, draw] (n1) at (0,0)   { };
		\node[vertex, fill=white, draw] (n2) at (0,1)   { };
		\node[vertex] (n3) at (-1.5,2)   { };
		\node[vertex] (n4) at (-0.5,2)   { };
		\node[vertex, fill=white, draw] (n5) at (0.5,2)   { };
		\node[vertex, fill=white, draw] (n6) at (1.5,2)   { };
		\node[vertex] (n7) at (0,3)   { };		

			
		\foreach \from/\to in {n1/n3, n2/n4, n7/n3, n7/n4, n7/n5, n7/n6, n3/n4, n4/n5}
    	\draw (\from) -- (\to);
		
    	
		
				
	\end{tikzpicture}

\end{center}

\medskip
\noindent
{\it Case} 1.1.1: One more edge is oriented (solid arrow) and this choice leads to a contradiction through repeated use of Lemma 1
(a cycle of four white vertices with three consecutively oriented edges in the final of the four diagrams below).

\begin{center}
	\begin{tikzpicture}
  		[scale=1,auto=left]
		
		\node[vertex, fill=white, draw] (n1) at (0,0)   { };
		\node[vertex] (n2) at (0,1)   { };
		\node[vertex, fill=white, draw] (n3) at (-1.5,2)   { };
		\node[vertex] (n4) at (-0.5,2)   { };
		\node[vertex] (n5) at (0.5,2)   { };
		\node[vertex, fill=white, draw] (n6) at (1.5,2)   { };
		\node[vertex, fill=white, draw] (n7) at (0,3)   { };		



		\draw [->]  (n1) -- (0,0.5);
		\draw (0,0.5) -- (n2);
		\draw [->] (n6) -- (0.75,1);
		\draw (0.75,1) -- (n1);
		\draw [->] (n6) -- (1,2);
		\draw (1,2) -- (n5);
		\draw [->] (n5) -- (0.25,1.5);
		\draw (0.25,1.5) -- (n2);
		\draw [-latex] (n7) -- (0.75,2.5);
		\draw (0.75,2.5) -- (n6);
		\draw [->>] (n7) -- (-0.75,2.5);
		\draw (-0.75,2.5) -- (n3);
		\draw [->>] (n3) -- (-0.75,1);
		\draw (-0.75,1) -- (n1);


					
		\foreach \from/\to in {n2/n4, n7/n4, n7/n5, n3/n4, n4/n5}
    	\draw (\from) -- (\to);
		
    	
		

		
		\node[vertex, fill=white, draw] (x1) at (4,0)   { };
		\node[vertex, fill=white, draw] (x2) at (4,1)   { };
		\node[vertex, fill=white, draw] (x3) at (2.5,2)   { };
		\node[vertex, fill=white, draw] (x4) at (3.5,2)   { };
		\node[vertex] (x5) at (4.5,2)   { };
		\node[vertex] (x6) at (5.5,2)   { };
		\node[vertex] (x7) at (4,3)   { };	

		\draw [->]  (x1) -- (4,0.5);
		\draw (4,0.5) -- (x2);
		\draw [->] (x6) -- (4.75,1);
		\draw (4.75,1) -- (x1);
		\draw [->]  (x6) -- (5,2);
		\draw (5,2) -- (x5);
		\draw [->] (x5) -- (4.25,1.5);
		\draw (4.25,1.5) -- (x2);
		\draw [->] (x7) -- (4.75,2.5);
		\draw (4.75,2.5) -- (x6);
		\draw [->] (x7) -- (3.25,2.5);
		\draw (3.25,2.5) -- (x3);
		\draw [->] (x3) -- (3.25,1);
		\draw (3.25,1) -- (x1);
		\draw [->>] (x3) -- (3,2);
		\draw (3,2) -- (x4);
		\draw [->>] (x4) -- (3.75,1.5);
		\draw (3.75,1.5) -- (x2);

	

			
		\foreach \from/\to in {x7/x4, x7/x5, x4/x5}
    	\draw (\from) -- (\to);



		\node[vertex] (y1) at (8,0)   { };
		\node[vertex] (y2) at (8,1)   { };
		\node[vertex, fill=white, draw] (y3) at (6.5,2)   { };
		\node[vertex, fill=white, draw] (y4) at (7.5,2)   { };
		\node[vertex, fill=white, draw] (y5) at (8.5,2)   { };
		\node[vertex] (y6) at (9.5,2)   { };
		\node[vertex, fill=white, draw] (y7) at (8,3)   { };	

		\draw [->]  (y1) -- (8,0.5);
		\draw (8,0.5) -- (y2);
		\draw [->] (y6) -- (8.75,1);
		\draw (8.75,1) -- (y1);
		\draw [->]  (y6) -- (9,2);
		\draw (9,2) -- (y5);
		\draw [->] (y5) -- (8.25,1.5);
		\draw (8.25,1.5) -- (y2);
		\draw [->] (y7) -- (8.75,2.5);
		\draw (8.75,2.5) -- (y6);
		\draw [->] (y7) -- (7.25,2.5);
		\draw (7.25,2.5) -- (y3);
		\draw [->] (y3) -- (7.25,1);
		\draw (7.25,1) -- (y1);
		\draw [->] (y3) -- (7,2);
		\draw (7,2) -- (y4);
		\draw [->] (y4) -- (7.75,1.5);
		\draw (7.75,1.5) -- (y2);
		\draw [->>] (y7) -- (8.25,2.5);
		\draw (8.25,2.5) -- (y5);
		\draw [->>] (y5) -- (8,2);
		\draw (8,2) -- (y4);

		\foreach \from/\to in {y7/y4}
    	\draw (\from) -- (\to);


		\node[vertex] (z1) at (12,0)   { };
		\node[vertex] (z2) at (12,1)   { };
		\node[vertex] (z3) at (10.5,2)   { };
		\node[vertex, fill=white, draw] (z4) at (11.5,2)   { };
		\node[vertex, fill=white, draw] (z5) at (12.5,2)   { };
		\node[vertex, fill=white, draw] (z6) at (13.5,2)   { };
		\node[vertex, fill=white, draw] (z7) at (12,3)   { };	

		\draw [->]  (z1) -- (12,0.5);
		\draw (12,0.5) -- (z2);
		\draw [->] (z6) -- (12.75,1);
		\draw (12.75,1) -- (z1);
		\draw [->]  (z6) -- (13,2);
		\draw (13,2) -- (z5);
		\draw [->] (z5) -- (12.25,1.5);
		\draw (12.25,1.5) -- (z2);
		\draw [->] (z7) -- (12.75,2.5);
		\draw (12.75,2.5) -- (z6);
		\draw [->] (z7) -- (11.25,2.5);
		\draw (11.25,2.5) -- (z3);
		\draw [->] (z3) -- (11.25,1);
		\draw (11.25,1) -- (z1);
		\draw [->] (z3) -- (11,2);
		\draw (11,2) -- (z4);
		\draw [->] (z4) -- (11.75,1.5);
		\draw (11.75,1.5) -- (z2);
		\draw [->] (z7) -- (12.25,2.5);
		\draw (12.25,2.5) -- (z5);
		\draw [->] (z5) -- (12,2);
		\draw (12,2) -- (z4);
		
		\foreach \from/\to in {z7/z4}
    	\draw (\from) -- (\to);		


			
		    	
						
	\end{tikzpicture}

\end{center}

\medskip
\noindent
{\it Case} 1.1.2: In this case the orientation of the edge chosen in Case 1.1.1 is reversed.

\begin{center}
	\begin{tikzpicture}
  		[scale=1,auto=left]
		
		\node[vertex] (n1) at (0,0)   { };
		\node[vertex] (n2) at (0,1)   { };
		\node[vertex] (n3) at (-1.5,2)   { };
		\node[vertex] (n4) at (-0.5,2)   { };
		\node[vertex] (n5) at (0.5,2)   { };
		\node[vertex] (n6) at (1.5,2)   { };
		\node[vertex] (n7) at (0,3)   { };		


		\draw [->]  (0,0) -- (0,0.5);
		\draw [->]  (0,0.5) -- (0,1);
		\draw [->]  (1.5,2) -- (0.75,1);
		\draw (0.75,1) -- (0,0);
		\draw [->]  (n6) -- (1,2);
		\draw (1,2) -- (n5);
		\draw [->]  (n5) -- (0.25,1.5);
		\draw (0.25,1.5) -- (n2);
		\draw [-latex] (n6) -- (0.75,2.5);
		\draw (0.75,2.5) -- (n7);
		

		
			
		\foreach \from/\to in {n1/n3, n2/n4, n7/n3, n7/n4, n7/n5, n3/n4, n4/n5}
    	\draw (\from) -- (\to);
		
    	
		
				
	\end{tikzpicture}

\end{center}

\medskip
\noindent
{\it Case} 1.1.2.1: By orienting one more edge (solid arrow) we obtain a contradiction through repeated use of Lemma 1 
(a cycle of four white vertices with three consecutively oriented edges in the final diagram).

\begin{center}
	\begin{tikzpicture}
  		[scale=1,auto=left]
		
		\node[vertex, fill=white, draw] (n1) at (0,0)   { };
		\node[vertex, fill=white, draw] (n2) at (0,1)   { };
		\node[vertex, fill=white, draw] (n3) at (-1.5,2)   { };
		\node[vertex, fill=white, draw] (n4) at (-0.5,2)   { };
		\node[vertex] (n5) at (0.5,2)   { };
		\node[vertex] (n6) at (1.5,2)   { };
		\node[vertex] (n7) at (0,3)   { };		



		\draw [->]  (n1) -- (0,0.5);
		\draw (0,0.5) -- (n2);
		\draw [->] (n6) -- (0.75,1);
		\draw (0.75,1) -- (n1);
		\draw [->] (n6) -- (1,2);
		\draw (1,2) -- (n5);
		\draw [->] (n5) -- (0.25,1.5);
		\draw (0.25,1.5) -- (n2);
		\draw [->] (n6) -- (0.75,2.5);
		\draw (0.75,2.5) -- (n7);
		\draw [-latex] (n2) -- (-0.25,1.5);
		\draw (-0.25,1.5) -- (n4);		
		\draw [->>] (n3) -- (-1,2);
		\draw (-1,2) -- (n4);
		\draw [->>] (n1) -- (-0.75,1);
		\draw (-0.75,1) -- (n3);


					
		\foreach \from/\to in {n7/n4, n7/n5, n4/n5, n3/n7}
    	\draw (\from) -- (\to);
		
    	
		

		
		\node[vertex] (x1) at (4,0)   { };
		\node[vertex, fill=white, draw] (x2) at (4,1)   { };
		\node[vertex] (x3) at (2.5,2)   { };
		\node[vertex, fill=white, draw] (x4) at (3.5,2)   { };
		\node[vertex, fill=white, draw] (x5) at (4.5,2)   { };
		\node[vertex] (x6) at (5.5,2)   { };
		\node[vertex, fill=white, draw] (x7) at (4,3)   { };	

		\draw [->]  (x1) -- (4,0.5);
		\draw (4,0.5) -- (x2);
		\draw [->] (x6) -- (4.75,1);
		\draw (4.75,1) -- (x1);
		\draw [->] (x6) -- (5,2);
		\draw (5,2) -- (x5);
		\draw [->] (x5) -- (4.25,1.5);
		\draw (4.25,1.5) -- (x2);
		\draw [->] (x6) -- (4.75,2.5);
		\draw (4.75,2.5) -- (x7);
		\draw [->] (x2) -- (3.75,1.5);
		\draw (3.75,1.5) -- (x4);		
		\draw [->] (x3) -- (3,2);
		\draw (3,2) -- (x4);
		\draw [->] (x1) -- (3.25,1);
		\draw (3.25,1) -- (x3);
		\draw [->>] (x5) -- (4.25,2.5);
		\draw (4.25,2.5) -- (x7);
		\draw [->>] (x7) -- (3.75,2.5);
		\draw (3.75,2.5) -- (x4);

	

			
		\foreach \from/\to in {x4/x5, x3/x7}
    	\draw (\from) -- (\to);



		\node[vertex, fill=white, draw] (y1) at (8,0)   { };
		\node[vertex] (y2) at (8,1)   { };
		\node[vertex, fill=white, draw] (y3) at (6.5,2)   { };
		\node[vertex] (y4) at (7.5,2)   { };
		\node[vertex] (y5) at (8.5,2)   { };
		\node[vertex, fill=white, draw] (y6) at (9.5,2)   { };
		\node[vertex, fill=white, draw] (y7) at (8,3)   { };	

		\draw [->]  (y1) -- (8,0.5);
		\draw (8,0.5) -- (y2);
		\draw [->] (y6) -- (8.75,1);
		\draw (8.75,1) -- (y1);
		\draw [->]  (y6) -- (9,2);
		\draw (9,2) -- (y5);
		\draw [->] (y5) -- (8.25,1.5);
		\draw (8.25,1.5) -- (y2);
		\draw [->] (y6) -- (8.75,2.5);
		\draw (8.75,2.5) -- (y7);
		\draw [->>] (y7) -- (7.25,2.5);
		\draw (7.25,2.5) -- (y3);
		\draw [->] (y1) -- (7.25,1);
		\draw (7.25,1) -- (y3);
		\draw [->] (y3) -- (7,2);
		\draw (7,2) -- (y4);
		\draw [->] (y2) -- (7.75,1.5);
		\draw (7.75,1.5) -- (y4);
		\draw [->] (y5) -- (8.25,2.5);
		\draw (8.25,2.5) -- (y7);
		\draw [->] (y7) -- (7.75,2.5);
		\draw (7.75,2.5) -- (y4);
		

		\foreach \from/\to in {y4/y5}
    	\draw (\from) -- (\to);


		\node[vertex] (z1) at (12,0)   { };
		\node[vertex] (z2) at (12,1)   { };
		\node[vertex, fill=white, draw] (z3) at (10.5,2)   { };
		\node[vertex, fill=white, draw] (z4) at (11.5,2)   { };
		\node[vertex, fill=white, draw] (z5) at (12.5,2)   { };
		\node[vertex] (z6) at (13.5,2)   { };
		\node[vertex, fill=white, draw] (z7) at (12,3)   { };	

		\draw [->]  (z1) -- (12,0.5);
		\draw (12,0.5) -- (z2);
		\draw [->] (z6) -- (12.75,1);
		\draw (12.75,1) -- (z1);
		\draw [->]  (z6) -- (13,2);
		\draw (13,2) -- (z5);
		\draw [->] (z5) -- (12.25,1.5);
		\draw (12.25,1.5) -- (z2);
		\draw [->] (z6) -- (12.75,2.5);
		\draw (12.75,2.5) -- (z7);
		\draw [->] (z7) -- (11.25,2.5);
		\draw (11.25,2.5) -- (z3);
		\draw [->] (z1) -- (11.25,1);
		\draw (11.25,1) -- (z3);
		\draw [->] (z3) -- (11,2);
		\draw (11,2) -- (z4);
		\draw [->] (z2) -- (11.75,1.5);
		\draw (11.75,1.5) -- (z4);
		\draw [->] (z5) -- (12.25,2.5);
		\draw (12.25,2.5) -- (z7);
		\draw [->] (z7) -- (11.75,2.5);
		\draw (11.75,2.5) -- (z4);
		

		\foreach \from/\to in {z4/z5}
    	\draw (\from) -- (\to);
		


			
		    	
						
	\end{tikzpicture}

\end{center}

\medskip
\noindent
{\it Case} 1.1.2.2: Now we reverse the orientation of the edge chosen in Case 1.1.2.1. 

\begin{center}
	\begin{tikzpicture}
  		[scale=1,auto=left]
		
		\node[vertex] (n1) at (0,0)   { };
		\node[vertex] (n2) at (0,1)   { };
		\node[vertex] (n3) at (-1.5,2)   { };
		\node[vertex] (n4) at (-0.5,2)   { };
		\node[vertex] (n5) at (0.5,2)   { };
		\node[vertex] (n6) at (1.5,2)   { };
		\node[vertex] (n7) at (0,3)   { };		


		\draw [->]  (0,0) -- (0,0.5);
		\draw [->]  (0,0.5) -- (0,1);
		\draw [->]  (1.5,2) -- (0.75,1);
		\draw (0.75,1) -- (0,0);
		\draw [->]  (n6) -- (1,2);
		\draw (1,2) -- (n5);
		\draw [->]  (n5) -- (0.25,1.5);
		\draw (0.25,1.5) -- (n2);
		\draw [->] (n6) -- (0.75,2.5);
		\draw (0.75,2.5) -- (n7);
		\draw [-latex] (n4) -- (-0.25,1.5);
		\draw (-0.25,1.5) -- (n2);

		
			
		\foreach \from/\to in {n1/n3, n7/n3, n7/n4, n7/n5, n3/n4, n4/n5}
    	\draw (\from) -- (\to);
		
    	
						
	\end{tikzpicture}

\end{center}

\medskip
\noindent
{\it Case} 1.1.2.2.1: By orienting one more edge (solid arrow) we obtain a contradiction through repeated use of Lemma 1.


\begin{center}
	\begin{tikzpicture}
  		[scale=1,auto=left]
		
		\node[vertex] (n1) at (0,0)   { };
		\node[vertex, fill=white, draw] (n2) at (0,1)   { };
		\node[vertex] (n3) at (-1.5,2)   { };
		\node[vertex, fill=white, draw] (n4) at (-0.5,2)   { };
		\node[vertex, fill=white, draw] (n5) at (0.5,2)   { };
		\node[vertex] (n6) at (1.5,2)   { };
		\node[vertex, fill=white, draw] (n7) at (0,3)   { };		



		\draw [->]  (n1) -- (0,0.5);
		\draw (0,0.5) -- (n2);
		\draw [->] (n6) -- (0.75,1);
		\draw (0.75,1) -- (n1);
		\draw [->] (n6) -- (1,2);
		\draw (1,2) -- (n5);
		\draw [->] (n5) -- (0.25,1.5);
		\draw (0.25,1.5) -- (n2);
		\draw [->] (n6) -- (0.75,2.5);
		\draw (0.75,2.5) -- (n7);
		\draw [->] (n4) -- (-0.25,1.5);
		\draw (-0.25,1.5) -- (n2);		
		\draw [-latex] (n7) -- (-0.25,2.5);
		\draw (-0.25,2.5) -- (n4);	
		\draw [->>] (n7) -- (0.25,2.5);
		\draw (0.25,2.5) -- (n5);	



					
		\foreach \from/\to in {n3/n1, n3/n4, n4/n5, n3/n7}
    	\draw (\from) -- (\to);
		
    	
		

		
		\node[vertex] (x1) at (4,0)   { };
		\node[vertex] (x2) at (4,1)   { };
		\node[vertex] (x3) at (2.5,2)   { };
		\node[vertex, fill=white, draw] (x4) at (3.5,2)   { };
		\node[vertex, fill=white, draw] (x5) at (4.5,2)   { };
		\node[vertex, fill=white, draw] (x6) at (5.5,2)   { };
		\node[vertex, fill=white, draw] (x7) at (4,3)   { };	

		\draw [->]  (x1) -- (4,0.5);
		\draw (4,0.5) -- (x2);
		\draw [->] (x6) -- (4.75,1);
		\draw (4.75,1) -- (x1);
		\draw [->] (x6) -- (5,2);
		\draw (5,2) -- (x5);
		\draw [->] (x5) -- (4.25,1.5);
		\draw (4.25,1.5) -- (x2);
		\draw [->] (x6) -- (4.75,2.5);
		\draw (4.75,2.5) -- (x7);
		\draw [->] (x4) -- (3.75,1.5);
		\draw (3.75,1.5) -- (x2);		
		\draw [->] (x7) -- (3.75,2.5);
		\draw (3.75,2.5) -- (x4);	
		\draw [->] (x7) -- (4.25,2.5);
		\draw (4.25,2.5) -- (x5);	
		\draw [->>] (x5) -- (4,2);
		\draw (4,2) -- (x4);	

	

			
		\foreach \from/\to in {x3/x4, x1/x3, x3/x7}
    	\draw (\from) -- (\to);



		\node[vertex] (y1) at (8,0)   { };
		\node[vertex] (y2) at (8,1)   { };
		\node[vertex, fill=white, draw] (y3) at (6.5,2)   { };
		\node[vertex, fill=white, draw] (y4) at (7.5,2)   { };
		\node[vertex, fill=white, draw] (y5) at (8.5,2)   { };
		\node[vertex] (y6) at (9.5,2)   { };
		\node[vertex, fill=white, draw] (y7) at (8,3)   { };	

		\draw [->]  (y1) -- (8,0.5);
		\draw (8,0.5) -- (y2);
		\draw [->] (y6) -- (8.75,1);
		\draw (8.75,1) -- (y1);
		\draw [->] (y6) -- (9,2);
		\draw (9,2) -- (y5);
		\draw [->] (y5) -- (8.25,1.5);
		\draw (8.25,1.5) -- (y2);
		\draw [->] (y6) -- (8.75,2.5);
		\draw (8.75,2.5) -- (y7);
		\draw [->] (y4) -- (7.75,1.5);
		\draw (7.75,1.5) -- (y2);		
		\draw [->] (y7) -- (7.75,2.5);
		\draw (7.75,2.5) -- (y4);	
		\draw [->] (y7) -- (8.25,2.5);
		\draw (8.25,2.5) -- (y5);	
		\draw [->] (y5) -- (8,2);
		\draw (8,2) -- (y4);	
		\draw [->>] (y7) -- (7.25,2.5);
		\draw (7.25,2.5) -- (y3);	
		\draw [->>] (y3) -- (7,2);
		\draw (7,2) -- (y4);


		

		\foreach \from/\to in {y1/y3}
    	\draw (\from) -- (\to);

			
		    	
						
		\node[vertex, fill=white, draw] (z1) at (2,-4)   { };
		\node[vertex, fill=white, draw] (z2) at (2,-3)   { };
		\node[vertex, fill=white, draw] (z3) at (0.5,-2)   { };
		\node[vertex, fill=white, draw] (z4) at (1.5,-2)   { };
		\node[vertex] (z5) at (2.5,-2)   { };
		\node[vertex] (z6) at (3.5,-2)   { };
		\node[vertex] (z7) at (2,-1)   { };		



		\draw [->]  (z1) -- (2,-3.5);
		\draw (2,-3.5) -- (z2);
		\draw [->] (z6) -- (2.75,-3);
		\draw (2.75,-3) -- (z1);
		\draw [->] (z6) -- (3,-2);
		\draw (3,-2) -- (z5);
		\draw [->] (z5) -- (2.25,-2.5);
		\draw (2.25,-2.5) -- (z2);
		\draw [->] (z6) -- (2.75,-1.5);
		\draw (2.75,-1.5) -- (z7);
		\draw [->] (z4) -- (1.75,-2.5);
		\draw (1.75,-2.5) -- (z2);		
		\draw [->] (z7) -- (1.75,-1.5);
		\draw (1.75,-1.5) -- (z4);	
		\draw [->] (z7) -- (2.25,-1.5);
		\draw (2.25,-1.5) -- (z5);	
		\draw [->] (z5) -- (2,-2);
		\draw (2,-2) -- (z4);	
		\draw [->] (z7) -- (1.25,-1.5);
		\draw (1.25,-1.5) -- (z3);	
		\draw [->] (z3) -- (1,-2);
		\draw (1,-2) -- (z4);
		\draw [->>] (z3) -- (1.25,-3);
		\draw (1.25,-3) -- (z1);


					
		
		
		\node[vertex, fill=white, draw] (w1) at (6,-4)   { };
		\node[vertex] (w2) at (6,-3)   { };
		\node[vertex, fill=white, draw] (w3) at (4.5,-2)   { };
		\node[vertex] (w4) at (5.5,-2)   { };
		\node[vertex] (w5) at (6.5,-2)   { };
		\node[vertex, fill=white, draw] (w6) at (7.5,-2)   { };
		\node[vertex, fill=white, draw] (w7) at (6,-1)   { };	

		\draw [->]  (w1) -- (6,-3.5);
		\draw (6,-3.5) -- (w2);
		\draw [->] (w6) -- (6.75,-3);
		\draw (6.75,-3) -- (w1);
		\draw [->] (w6) -- (7,-2);
		\draw (7,-2) -- (w5);
		\draw [->] (w5) -- (6.25,-2.5);
		\draw (6.25,-2.5) -- (w2);
		\draw [->] (w6) -- (6.75,-1.5);
		\draw (6.75,-1.5) -- (w7);
		\draw [->] (w4) -- (5.75,-2.5);
		\draw (5.75,-2.5) -- (w2);		
		\draw [->] (w7) -- (5.75,-1.5);
		\draw (5.75,-1.5) -- (w4);	
		\draw [->] (w7) -- (6.25,-1.5);
		\draw (6.25,-1.5) -- (w5);	
		\draw [->] (w5) -- (6,-2);
		\draw (6,-2) -- (w4);	
		\draw [->] (w7) -- (5.25,-1.5);
		\draw (5.25,-1.5) -- (w3);	
		\draw [->] (w3) -- (5,-2);
		\draw (5,-2) -- (w4);
		\draw [->] (w3) -- (5.25,-3);
		\draw (5.25,-3) -- (w1);



				
		    	
		
				
	\end{tikzpicture}

\end{center}

\medskip
\noindent
{\it Case} 1.1.2.2.2: By reversing the orientation of the edge chosen in Case 1.1.2.2.1 we obtain a contradiction again. This completes 
the analysis of Case 1.1.

\begin{center}
	\begin{tikzpicture}
  		[scale=1,auto=left]
		
		\node[vertex] (n1) at (0,0)   { };
		\node[vertex, fill=white, draw] (n2) at (0,1)   { };
		\node[vertex] (n3) at (-1.5,2)   { };
		\node[vertex, fill=white, draw] (n4) at (-0.5,2)   { };
		\node[vertex, fill=white, draw] (n5) at (0.5,2)   { };
		\node[vertex] (n6) at (1.5,2)   { };
		\node[vertex, fill=white, draw] (n7) at (0,3)   { };		



		\draw [->]  (n1) -- (0,0.5);
		\draw (0,0.5) -- (n2);
		\draw [->] (n6) -- (0.75,1);
		\draw (0.75,1) -- (n1);
		\draw [->] (n6) -- (1,2);
		\draw (1,2) -- (n5);
		\draw [->] (n5) -- (0.25,1.5);
		\draw (0.25,1.5) -- (n2);
		\draw [->] (n6) -- (0.75,2.5);
		\draw (0.75,2.5) -- (n7);
		\draw [->] (n4) -- (-0.25,1.5);
		\draw (-0.25,1.5) -- (n2);		
		\draw [-latex] (n4) -- (-0.25,2.5);
		\draw (-0.25,2.5) -- (n7);	
		\draw [->>] (n5) -- (0.25,2.5);
		\draw (0.25,2.5) -- (n7);	



					
		\foreach \from/\to in {n3/n1, n3/n4, n4/n5, n3/n7}
    	\draw (\from) -- (\to);
		
    	
		

		
		\node[vertex] (x1) at (4,0)   { };
		\node[vertex] (x2) at (4,1)   { };
		\node[vertex] (x3) at (2.5,2)   { };
		\node[vertex, fill=white, draw] (x4) at (3.5,2)   { };
		\node[vertex, fill=white, draw] (x5) at (4.5,2)   { };
		\node[vertex, fill=white, draw] (x6) at (5.5,2)   { };
		\node[vertex, fill=white, draw] (x7) at (4,3)   { };	

		\draw [->]  (x1) -- (4,0.5);
		\draw (4,0.5) -- (x2);
		\draw [->] (x6) -- (4.75,1);
		\draw (4.75,1) -- (x1);
		\draw [->] (x6) -- (5,2);
		\draw (5,2) -- (x5);
		\draw [->] (x5) -- (4.25,1.5);
		\draw (4.25,1.5) -- (x2);
		\draw [->] (x6) -- (4.75,2.5);
		\draw (4.75,2.5) -- (x7);
		\draw [->] (x4) -- (3.75,1.5);
		\draw (3.75,1.5) -- (x2);		
		\draw [->] (x4) -- (3.75,2.5);
		\draw (3.75,2.5) -- (x7);	
		\draw [->] (x5) -- (4.25,2.5);
		\draw (4.25,2.5) -- (x7);	
		\draw [->>] (x4) -- (4,2);
		\draw (4,2) -- (x5);	

	

			
		\foreach \from/\to in {x3/x4, x1/x3, x3/x7}
    	\draw (\from) -- (\to);



		\node[vertex] (y1) at (8,0)   { };
		\node[vertex] (y2) at (8,1)   { };
		\node[vertex, fill=white, draw] (y3) at (6.5,2)   { };
		\node[vertex, fill=white, draw] (y4) at (7.5,2)   { };
		\node[vertex, fill=white, draw] (y5) at (8.5,2)   { };
		\node[vertex] (y6) at (9.5,2)   { };
		\node[vertex, fill=white, draw] (y7) at (8,3)   { };	

		\draw [->]  (y1) -- (8,0.5);
		\draw (8,0.5) -- (y2);
		\draw [->] (y6) -- (8.75,1);
		\draw (8.75,1) -- (y1);
		\draw [->] (y6) -- (9,2);
		\draw (9,2) -- (y5);
		\draw [->] (y5) -- (8.25,1.5);
		\draw (8.25,1.5) -- (y2);
		\draw [->] (y6) -- (8.75,2.5);
		\draw (8.75,2.5) -- (y7);
		\draw [->] (y4) -- (7.75,1.5);
		\draw (7.75,1.5) -- (y2);		
		\draw [->] (y4) -- (7.75,2.5);
		\draw (7.75,2.5) -- (y7);	
		\draw [->] (y5) -- (8.25,2.5);
		\draw (8.25,2.5) -- (y7);	
		\draw [->] (y4) -- (8,2);
		\draw (8,2) -- (y5);	
		\draw [->>] (y3) -- (7.25,2.5);
		\draw (7.25,2.5) -- (y7);	
		\draw [->>] (y4) -- (7,2);
		\draw (7,2) -- (y3);


		

		\foreach \from/\to in {y1/y3}
    	\draw (\from) -- (\to);

			
		    	
						
		\node[vertex, fill=white, draw] (z1) at (2,-4)   { };
		\node[vertex, fill=white, draw] (z2) at (2,-3)   { };
		\node[vertex, fill=white, draw] (z3) at (0.5,-2)   { };
		\node[vertex, fill=white, draw] (z4) at (1.5,-2)   { };
		\node[vertex] (z5) at (2.5,-2)   { };
		\node[vertex] (z6) at (3.5,-2)   { };
		\node[vertex] (z7) at (2,-1)   { };		



		\draw [->]  (z1) -- (2,-3.5);
		\draw (2,-3.5) -- (z2);
		\draw [->] (z6) -- (2.75,-3);
		\draw (2.75,-3) -- (z1);
		\draw [->] (z6) -- (3,-2);
		\draw (3,-2) -- (z5);
		\draw [->] (z5) -- (2.25,-2.5);
		\draw (2.25,-2.5) -- (z2);
		\draw [->] (z6) -- (2.75,-1.5);
		\draw (2.75,-1.5) -- (z7);
		\draw [->] (z4) -- (1.75,-2.5);
		\draw (1.75,-2.5) -- (z2);		
		\draw [->] (z4) -- (1.75,-1.5);
		\draw (1.75,-1.5) -- (z7);	
		\draw [->] (z5) -- (2.25,-1.5);
		\draw (2.25,-1.5) -- (z7);	
		\draw [->] (z4) -- (2,-2);
		\draw (2,-2) -- (z5);	
		\draw [->] (z3) -- (1.25,-1.5);
		\draw (1.25,-1.5) -- (z7);	
		\draw [->] (z4) -- (1,-2);
		\draw (1,-2) -- (z3);
		\draw [->>] (z1) -- (1.25,-3);
		\draw (1.25,-3) -- (z3);


					
		
		
		\node[vertex, fill=white, draw] (w1) at (6,-4)   { };
		\node[vertex] (w2) at (6,-3)   { };
		\node[vertex, fill=white, draw] (w3) at (4.5,-2)   { };
		\node[vertex] (w4) at (5.5,-2)   { };
		\node[vertex] (w5) at (6.5,-2)   { };
		\node[vertex, fill=white, draw] (w6) at (7.5,-2)   { };
		\node[vertex, fill=white, draw] (w7) at (6,-1)   { };	

		\draw [->]  (w1) -- (6,-3.5);
		\draw (6,-3.5) -- (w2);
		\draw [->] (w6) -- (6.75,-3);
		\draw (6.75,-3) -- (w1);
		\draw [->] (w6) -- (7,-2);
		\draw (7,-2) -- (w5);
		\draw [->] (w5) -- (6.25,-2.5);
		\draw (6.25,-2.5) -- (w2);
		\draw [->] (w6) -- (6.75,-1.5);
		\draw (6.75,-1.5) -- (w7);
		\draw [->] (w4) -- (5.75,-2.5);
		\draw (5.75,-2.5) -- (w2);		
		\draw [->] (w4) -- (5.75,-1.5);
		\draw (5.75,-1.5) -- (w7);	
		\draw [->] (w5) -- (6.25,-1.5);
		\draw (6.25,-1.5) -- (w7);	
		\draw [->] (w4) -- (6,-2);
		\draw (6,-2) -- (w5);	
		\draw [->] (w3) -- (5.25,-1.5);
		\draw (5.25,-1.5) -- (w7);	
		\draw [->] (w4) -- (5,-2);
		\draw (5,-2) -- (w3);
		\draw [->] (w1) -- (5.25,-3);
		\draw (5.25,-3) -- (w3);



				
		    	
				
	\end{tikzpicture}

\end{center}

\medskip
\noindent
{\it Case} 1.2: The orientation of the edge chosen in Case 1.1 is reversed. 

\begin{center}
	\begin{tikzpicture}
  		[scale=1,auto=left]
		
		
		\node[vertex] (n1) at (0,0)   { };
		\node[vertex] (n2) at (0,1)   { };
		\node[vertex] (n3) at (-1.5,2)   { };
		\node[vertex] (n4) at (-0.5,2)   { };
		\node[vertex] (n5) at (0.5,2)   { };
		\node[vertex] (n6) at (1.5,2)   { };
		\node[vertex] (n7) at (0,3)   { };		


		\draw [->]  (0,0) -- (0,0.5);
		\draw [->]  (0,0.5) -- (0,1);
		\draw [-latex] (n1) -- (0.75,1);
		\draw (0.75,1) -- (n6);
		

	
		\foreach \from/\to in {n1/n3, n2/n4, n7/n3, n7/n4, n2/n5, n5/n6, n7/n5, n7/n6, n3/n4, n4/n5}
    	\draw (\from) -- (\to);
		
    	
		
				
	\end{tikzpicture}

\end{center}

\medskip
\noindent
{\it Case} 1.2.1: We orient one more edge (solid arrow) and derive one consequence (double arrow).

\begin{center}
	\begin{tikzpicture}
  		[scale=1,auto=left]
		
		
		\node[vertex, fill=white, draw] (n1) at (0,0)   { };
		\node[vertex, fill=white, draw] (n2) at (0,1)   { };
		\node[vertex] (n3) at (-1.5,2)   { };
		\node[vertex] (n4) at (-0.5,2)   { };
		\node[vertex, fill=white, draw] (n5) at (0.5,2)   { };
		\node[vertex, fill=white, draw] (n6) at (1.5,2)   { };
		\node[vertex] (n7) at (0,3)   { };		


		\draw [->]  (n1) -- (0,0.5);
		\draw (0,0.5) -- (n2);
		\draw [->]  (n1) -- (0.75,1);
		\draw (0.75,1) -- (n6);
		\draw [-latex] (n2) -- (0.25,1.5);
		\draw (0.25,1.5) -- (n5);
		\draw [->>] (n6) -- (1,2);
		\draw (1,2) -- (n5);


	
		\foreach \from/\to in {n1/n3, n2/n4, n7/n3, n7/n4, n7/n5, n7/n6, n3/n4, n4/n5}
    	\draw (\from) -- (\to);
		
    	
		
				
	\end{tikzpicture}

\end{center}

\medskip
\noindent
{\it Case} 1.2.1.1: One more edge is oriented (solid arrow) leading to a contradiction. 

\begin{center}
	\begin{tikzpicture}
  		[scale=1,auto=left]
		
		\node[vertex] (n1) at (0,0)   { };
		\node[vertex, fill=white, draw] (n2) at (0,1)   { };
		\node[vertex] (n3) at (-1.5,2)   { };
		\node[vertex, fill=white, draw] (n4) at (-0.5,2)   { };
		\node[vertex, fill=white, draw] (n5) at (0.5,2)   { };
		\node[vertex] (n6) at (1.5,2)   { };
		\node[vertex, fill=white, draw] (n7) at (0,3)   { };		



		\draw [->]  (n1) -- (0,0.5);
		\draw (0,0.5) -- (n2);
		\draw [->]  (n1) -- (0.75,1);
		\draw (0.75,1) -- (n6);
		\draw [->] (n2) -- (0.25,1.5);
		\draw (0.25,1.5) -- (n5);
		\draw [->] (n6) -- (1,2);
		\draw (1,2) -- (n5);
		\draw [-latex] (n5) -- (0.25,2.5);
		\draw (0.25,2.5) -- (n7);
		\draw [->>] (n2) -- (-0.25,1.5);
		\draw (-0.25,1.5) -- (n4);
		\draw [->>] (n4) -- (-0.25,2.5);
		\draw (-0.25,2.5) -- (n7);



		\foreach \from/\to in {n1/n3, n7/n3, n7/n6, n3/n4, n4/n5}
    	\draw (\from) -- (\to);
		
    	
		

		
		\node[vertex, fill=white, draw] (x1) at (4,0)   { };
		\node[vertex, fill=white, draw] (x2) at (4,1)   { };
		\node[vertex, fill=white, draw] (x3) at (2.5,2)   { };
		\node[vertex, fill=white, draw] (x4) at (3.5,2)   { };
		\node[vertex] (x5) at (4.5,2)   { };
		\node[vertex] (x6) at (5.5,2)   { };
		\node[vertex] (x7) at (4,3)   { };	

		\draw [->]  (x1) -- (4,0.5);
		\draw (4,0.5) -- (x2);
		\draw [->]  (x1) -- (4.75,1);
		\draw (4.75,1) -- (x6);
		\draw [->] (x2) -- (4.25,1.5);
		\draw (4.25,1.5) -- (x5);
		\draw [->] (x6) -- (5,2);
		\draw (5,2) -- (x5);
		\draw [->] (x5) -- (4.25,2.5);
		\draw (4.25,2.5) -- (x7);
		\draw [->] (x2) -- (3.75,1.5);
		\draw (3.75,1.5) -- (x4);
		\draw [->] (x4) -- (3.75,2.5);
		\draw (3.75,2.5) -- (x7);
		\draw [->>] (x1) -- (3.25,1);
		\draw (3.25,1) -- (x3);
		\draw [->>] (x3) -- (3,2);
		\draw (3,2) -- (x4);



		\foreach \from/\to in {x7/x3, x7/x6, x4/x5}
    	\draw (\from) -- (\to);
		



		\node[vertex] (y1) at (8,0)   { };
		\node[vertex] (y2) at (8,1)   { };
		\node[vertex] (y3) at (6.5,2)   { };
		\node[vertex, fill=white, draw] (y4) at (7.5,2)   { };
		\node[vertex, fill=white, draw] (y5) at (8.5,2)   { };
		\node[vertex, fill=white, draw] (y6) at (9.5,2)   { };
		\node[vertex, fill=white, draw] (y7) at (8,3)   { };	

		\draw [->]  (y1) -- (8,0.5);
		\draw (8,0.5) -- (y2);
		\draw [->] (y1) -- (8.75,1);
		\draw (8.75,1) -- (y6);
		\draw [->]  (y6) -- (9,2);
		\draw (9,2) -- (y5);
		\draw [->] (y2) -- (8.25,1.5);
		\draw (8.25,1.5) -- (y5);
		\draw [->] (y1) -- (7.25,1);
		\draw (7.25,1) -- (y3);
		\draw [->] (y3) -- (7,2);
		\draw (7,2) -- (y4);
		\draw [->] (y2) -- (7.75,1.5);
		\draw (7.75,1.5) -- (y4);
		\draw [->] (y5) -- (8.25,2.5);
		\draw (8.25,2.5) -- (y7);
		\draw [->] (y4) -- (7.75,2.5);
		\draw (7.75,2.5) -- (y7);
		\draw [->>] (y4) -- (8,2);
		\draw (8,2) -- (y5);


		\foreach \from/\to in {y7/y3, y6/y7}
    	\draw (\from) -- (\to);


		\node[vertex] (z1) at (12,0)   { };
		\node[vertex] (z2) at (12,1)   { };
		\node[vertex, fill=white, draw] (z3) at (10.5,2)   { };
		\node[vertex, fill=white, draw] (z4) at (11.5,2)   { };
		\node[vertex, fill=white, draw] (z5) at (12.5,2)   { };
		\node[vertex] (z6) at (13.5,2)   { };
		\node[vertex, fill=white, draw] (z7) at (12,3)   { };	

		\draw [->]  (z1) -- (12,0.5);
		\draw (12,0.5) -- (z2);
		\draw [->] (z1) -- (12.75,1);
		\draw (12.75,1) -- (z6);
		\draw [->]  (z6) -- (13,2);
		\draw (13,2) -- (z5);
		\draw [->] (z2) -- (12.25,1.5);
		\draw (12.25,1.5) -- (z5);
		\draw [->] (z1) -- (11.25,1);
		\draw (11.25,1) -- (z3);
		\draw [->] (z3) -- (11,2);
		\draw (11,2) -- (z4);
		\draw [->] (z2) -- (11.75,1.5);
		\draw (11.75,1.5) -- (z4);
		\draw [->] (z5) -- (12.25,2.5);
		\draw (12.25,2.5) -- (z7);
		\draw [->] (z4) -- (11.75,2.5);
		\draw (11.75,2.5) -- (z7);
		\draw [->] (z4) -- (12,2);
		\draw (12,2) -- (z5);

		\foreach \from/\to in {z6/z7, z3/z7}
    	\draw (\from) -- (\to);
		


			
		    	
		
				
	\end{tikzpicture}

\end{center}

\medskip
\noindent
{\it Case} 1.2.1.2: The orientation of the edge chosen in Case 1.2.1.1 is reversed. 

\begin{center}
	\begin{tikzpicture}
  		[scale=1,auto=left]
		
		\node[vertex] (n1) at (0,0)   { };
		\node[vertex] (n2) at (0,1)   { };
		\node[vertex] (n3) at (-1.5,2)   { };
		\node[vertex] (n4) at (-0.5,2)   { };
		\node[vertex] (n5) at (0.5,2)   { };
		\node[vertex] (n6) at (1.5,2)   { };
		\node[vertex] (n7) at (0,3)   { };		



		\draw [->]  (n1) -- (0,0.5);
		\draw (0,0.5) -- (n2);
		\draw [->]  (n1) -- (0.75,1);
		\draw (0.75,1) -- (n6);
		\draw [->] (n2) -- (0.25,1.5);
		\draw (0.25,1.5) -- (n5);
		\draw [->] (n6) -- (1,2);
		\draw (1,2) -- (n5);
		\draw [-latex] (n7) -- (0.25,2.5);
		\draw (0.25,2.5) -- (n5);




		\foreach \from/\to in {n1/n3, n7/n3, n7/n6, n3/n4, n4/n5, n2/n4, n4/n7}
    	\draw (\from) -- (\to);

	    	
		
				
	\end{tikzpicture}

\end{center}

\medskip
\noindent
{\it Case} 1.2.1.2.1: One more edge is oriented (solid arrow) leading to a contradiction.  

\begin{center}
	\begin{tikzpicture}
  		[scale=1,auto=left]
		
		\node[vertex, fill=white, draw] (n1) at (0,0)   { };
		\node[vertex] (n2) at (0,1)   { };
		\node[vertex, fill=white, draw] (n3) at (-1.5,2)   { };
		\node[vertex] (n4) at (-0.5,2)   { };
		\node[vertex] (n5) at (0.5,2)   { };
		\node[vertex, fill=white, draw] (n6) at (1.5,2)   { };
		\node[vertex, fill=white, draw] (n7) at (0,3)   { };		



		\draw [->]  (n1) -- (0,0.5);
		\draw (0,0.5) -- (n2);
		\draw [->] (n1) -- (0.75,1);
		\draw (0.75,1) -- (n6);
		\draw [->] (n6) -- (1,2);
		\draw (1,2) -- (n5);
		\draw [->] (n2) -- (0.25,1.5);
		\draw (0.25,1.5) -- (n5);
		\draw [-latex] (n6) -- (0.75,2.5);
		\draw (0.75,2.5) -- (n7);
		\draw [->] (n7) -- (0.25,2.5);
		\draw (0.25,2.5) -- (n5);	
		\draw [->>] (n1) -- (-0.75,1);
		\draw (-0.75,1) -- (n3);
		\draw [->>] (n3) -- (-0.75,2.5);
		\draw (-0.75,2.5) -- (n7);	


					
		\foreach \from/\to in {n2/n4, n4/n7, n3/n4, n4/n5}
    	\draw (\from) -- (\to);
		
    	
		

		
		\node[vertex] (x1) at (4,0)   { };
		\node[vertex] (x2) at (4,1)   { };
		\node[vertex, fill=white, draw] (x3) at (2.5,2)   { };
		\node[vertex, fill=white, draw] (x4) at (3.5,2)   { };
		\node[vertex, fill=white, draw] (x5) at (4.5,2)   { };
		\node[vertex] (x6) at (5.5,2)   { };
		\node[vertex, fill=white, draw] (x7) at (4,3)   { };	

		\draw [->]  (x1) -- (4,0.5);
		\draw (4,0.5) -- (x2);
		\draw [->] (x1) -- (4.75,1);
		\draw (4.75,1) -- (x6);
		\draw [->] (x6) -- (5,2);
		\draw (5,2) -- (x5);
		\draw [->] (x2) -- (4.25,1.5);
		\draw (4.25,1.5) -- (x5);
		\draw [->] (x6) -- (4.75,2.5);
		\draw (4.75,2.5) -- (x7);
		\draw [->] (x7) -- (4.25,2.5);
		\draw (4.25,2.5) -- (x5);	
		\draw [->>] (x4) -- (4,2);
		\draw (4,2) -- (x5);	
		\draw [->] (x1) -- (3.25,1);
		\draw (3.25,1) -- (x3);
		\draw [->] (x3) -- (3.25,2.5);
		\draw (3.25,2.5) -- (x7);
		\draw [->>] (x3) -- (3,2);
		\draw (3,2) -- (x4);


			
		\foreach \from/\to in {x2/x4, x4/x7, x1/x3, x3/x7}
    	\draw (\from) -- (\to);



		\node[vertex] (y1) at (8,0)   { };
		\node[vertex] (y2) at (8,1)   { };
		\node[vertex] (y3) at (6.5,2)   { };
		\node[vertex, fill=white, draw] (y4) at (7.5,2)   { };
		\node[vertex, fill=white, draw] (y5) at (8.5,2)   { };
		\node[vertex, fill=white, draw] (y6) at (9.5,2)   { };
		\node[vertex, fill=white, draw] (y7) at (8,3)   { };	

		\draw [->]  (y1) -- (8,0.5);
		\draw (8,0.5) -- (y2);
		\draw [->] (y1) -- (8.75,1);
		\draw (8.75,1) -- (y6);
		\draw [->] (y6) -- (9,2);
		\draw (9,2) -- (y5);
		\draw [->] (y2) -- (8.25,1.5);
		\draw (8.25,1.5) -- (y5);
		\draw [->] (y6) -- (8.75,2.5);
		\draw (8.75,2.5) -- (y7);
		\draw [->>] (y4) -- (7.75,2.5);
		\draw (7.75,2.5) -- (y7);	
		\draw [->] (y7) -- (8.25,2.5);
		\draw (8.25,2.5) -- (y5);	
		\draw [->] (y4) -- (8,2);
		\draw (8,2) -- (y5);	
		\draw [->] (y3) -- (7.25,2.5);
		\draw (7.25,2.5) -- (y7);	
		\draw [->] (y3) -- (7,2);
		\draw (7,2) -- (y4);
		\draw [->] (y1) -- (7.25,1);
		\draw (7.25,1) -- (y3);

		

		\foreach \from/\to in {y2/y4}
    	\draw (\from) -- (\to);

			
		    	
						
		\node[vertex] (z1) at (2,-4)   { };
		\node[vertex, fill=white, draw] (z2) at (2,-3)   { };
		\node[vertex] (z3) at (0.5,-2)   { };
		\node[vertex, fill=white, draw] (z4) at (1.5,-2)   { };
		\node[vertex, fill=white, draw] (z5) at (2.5,-2)   { };
		\node[vertex] (z6) at (3.5,-2)   { };
		\node[vertex, fill=white, draw] (z7) at (2,-1)   { };		



		\draw [->]  (z1) -- (2,-3.5);
		\draw (2,-3.5) -- (z2);
		\draw [->] (z1) -- (2.75,-3);
		\draw (2.75,-3) -- (z6);
		\draw [->] (z6) -- (3,-2);
		\draw (3,-2) -- (z5);
		\draw [->] (z2) -- (2.25,-2.5);
		\draw (2.25,-2.5) -- (z5);
		\draw [->] (z6) -- (2.75,-1.5);
		\draw (2.75,-1.5) -- (z7);
		\draw [->>] (z4) -- (1.75,-2.5);
		\draw (1.75,-2.5) -- (z2);		
		\draw [->] (z4) -- (1.75,-1.5);
		\draw (1.75,-1.5) -- (z7);	
		\draw [->] (z7) -- (2.25,-1.5);
		\draw (2.25,-1.5) -- (z5);	
		\draw [->] (z4) -- (2,-2);
		\draw (2,-2) -- (z5);	
		\draw [->] (z3) -- (1.25,-1.5);
		\draw (1.25,-1.5) -- (z7);	
		\draw [->] (z3) -- (1,-2);
		\draw (1,-2) -- (z4);
		\draw [->] (z1) -- (1.25,-3);
		\draw (1.25,-3) -- (z3);


					
		
		
		\node[vertex, fill=white, draw] (w1) at (6,-4)   { };
		\node[vertex, fill=white, draw] (w2) at (6,-3)   { };
		\node[vertex, fill=white, draw] (w3) at (4.5,-2)   { };
		\node[vertex, fill=white, draw] (w4) at (5.5,-2)   { };
		\node[vertex] (w5) at (6.5,-2)   { };
		\node[vertex] (w6) at (7.5,-2)   { };
		\node[vertex] (w7) at (6,-1)   { };	

		\draw [->]  (w1) -- (6,-3.5);
		\draw (6,-3.5) -- (w2);
		\draw [->] (w1) -- (6.75,-3);
		\draw (6.75,-3) -- (w6);
		\draw [->] (w6) -- (7,-2);
		\draw (7,-2) -- (w5);
		\draw [->] (w2) -- (6.25,-2.5);
		\draw (6.25,-2.5) -- (w5);
		\draw [->] (w6) -- (6.75,-1.5);
		\draw (6.75,-1.5) -- (w7);
		\draw [->] (w4) -- (5.75,-2.5);
		\draw (5.75,-2.5) -- (w2);		
		\draw [->] (w4) -- (5.75,-1.5);
		\draw (5.75,-1.5) -- (w7);	
		\draw [->] (w7) -- (6.25,-1.5);
		\draw (6.25,-1.5) -- (w5);	
		\draw [->] (w4) -- (6,-2);
		\draw (6,-2) -- (w5);	
		\draw [->] (w3) -- (5.25,-1.5);
		\draw (5.25,-1.5) -- (w7);	
		\draw [->] (w3) -- (5,-2);
		\draw (5,-2) -- (w4);
		\draw [->] (w1) -- (5.25,-3);
		\draw (5.25,-3) -- (w3);



				
		    	
		
				
	\end{tikzpicture}

\end{center}

\medskip
\noindent
{\it Case} 1.2.1.2.2: The orientation of the edge chosen in Case 1.2.1.2.1 is reversed leading a contradiction again. This 
completes the analysis of Case 1.2.1.

\begin{center}
	\begin{tikzpicture}
  		[scale=1,auto=left]
		
		\node[vertex] (n1) at (0,0)   { };
		\node[vertex] (n2) at (0,1)   { };
		\node[vertex] (n3) at (-1.5,2)   { };
		\node[vertex, fill=white, draw] (n4) at (-0.5,2)   { };
		\node[vertex, fill=white, draw] (n5) at (0.5,2)   { };
		\node[vertex, fill=white, draw] (n6) at (1.5,2)   { };
		\node[vertex, fill=white, draw] (n7) at (0,3)   { };		



		\draw [->]  (n1) -- (0,0.5);
		\draw (0,0.5) -- (n2);
		\draw [->] (n1) -- (0.75,1);
		\draw (0.75,1) -- (n6);
		\draw [->] (n6) -- (1,2);
		\draw (1,2) -- (n5);
		\draw [->] (n2) -- (0.25,1.5);
		\draw (0.25,1.5) -- (n5);
		\draw [-latex] (n7) -- (0.75,2.5);
		\draw (0.75,2.5) -- (n6);
		\draw [->] (n7) -- (0.25,2.5);
		\draw (0.25,2.5) -- (n5);	
		\draw [->>] (n4) -- (0,2);
		\draw (0,2) -- (n5);
		\draw [->>] (n7) -- (-0.25,2.5);
		\draw (-0.25,2.5) -- (n4);	


					
		\foreach \from/\to in {n2/n4, n3/n7, n3/n4, n1/n3}
    	\draw (\from) -- (\to);
		
    	
		

		
		\node[vertex] (x1) at (4,0)   { };
		\node[vertex, fill=white, draw] (x2) at (4,1)   { };
		\node[vertex] (x3) at (2.5,2)   { };
		\node[vertex, fill=white, draw] (x4) at (3.5,2)   { };
		\node[vertex, fill=white, draw] (x5) at (4.5,2)   { };
		\node[vertex] (x6) at (5.5,2)   { };
		\node[vertex, fill=white, draw] (x7) at (4,3)   { };	

		\draw [->]  (x1) -- (4,0.5);
		\draw (4,0.5) -- (x2);
		\draw [->] (x1) -- (4.75,1);
		\draw (4.75,1) -- (x6);
		\draw [->] (x6) -- (5,2);
		\draw (5,2) -- (x5);
		\draw [->] (x2) -- (4.25,1.5);
		\draw (4.25,1.5) -- (x5);
		\draw [->] (x7) -- (4.75,2.5);
		\draw (4.75,2.5) -- (x6);
		\draw [->] (x7) -- (4.25,2.5);
		\draw (4.25,2.5) -- (x5);	
		\draw [->] (x4) -- (4,2);
		\draw (4,2) -- (x5);	
		\draw [->] (x7) -- (3.75,2.5);
		\draw (3.75,2.5) -- (x4);
		\draw [->>] (x2) -- (3.75,1.5);
		\draw (3.75,1.5) -- (x4);


			
		\foreach \from/\to in {x3/x4, x1/x3, x3/x7, x1/x3, x3/x7}
    	\draw (\from) -- (\to);



		\node[vertex, fill=white, draw] (y1) at (8,0)   { };
		\node[vertex, fill=white, draw] (y2) at (8,1)   { };
		\node[vertex, fill=white, draw] (y3) at (6.5,2)   { };
		\node[vertex, fill=white, draw] (y4) at (7.5,2)   { };
		\node[vertex] (y5) at (8.5,2)   { };
		\node[vertex] (y6) at (9.5,2)   { };
		\node[vertex] (y7) at (8,3)   { };	

		\draw [->]  (y1) -- (8,0.5);
		\draw (8,0.5) -- (y2);
		\draw [->] (y1) -- (8.75,1);
		\draw (8.75,1) -- (y6);
		\draw [->] (y6) -- (9,2);
		\draw (9,2) -- (y5);
		\draw [->] (y2) -- (8.25,1.5);
		\draw (8.25,1.5) -- (y5);
		\draw [->] (y7) -- (8.75,2.5);
		\draw (8.75,2.5) -- (y6);
		\draw [->] (y7) -- (7.75,2.5);
		\draw (7.75,2.5) -- (y4);	
		\draw [->] (y7) -- (8.25,2.5);
		\draw (8.25,2.5) -- (y5);	
		\draw [->] (y4) -- (8,2);
		\draw (8,2) -- (y5);	
		\draw [->] (y2) -- (7.75,1.5);
		\draw (7.75,1.5) -- (y4);	
		\draw [->>] (y3) -- (7,2);
		\draw (7,2) -- (y4);
		\draw [->>] (y1) -- (7.25,1);
		\draw (7.25,1) -- (y3);

		

		\foreach \from/\to in {y3/y7}
    	\draw (\from) -- (\to);

			
		    	
						
		\node[vertex, fill=white, draw] (z1) at (2,-4)   { };
		\node[vertex] (z2) at (2,-3)   { };
		\node[vertex, fill=white, draw] (z3) at (0.5,-2)   { };
		\node[vertex] (z4) at (1.5,-2)   { };
		\node[vertex] (z5) at (2.5,-2)   { };
		\node[vertex, fill=white, draw] (z6) at (3.5,-2)   { };
		\node[vertex, fill=white, draw] (z7) at (2,-1)   { };		



		\draw [->]  (z1) -- (2,-3.5);
		\draw (2,-3.5) -- (z2);
		\draw [->] (z1) -- (2.75,-3);
		\draw (2.75,-3) -- (z6);
		\draw [->] (z6) -- (3,-2);
		\draw (3,-2) -- (z5);
		\draw [->] (z2) -- (2.25,-2.5);
		\draw (2.25,-2.5) -- (z5);
		\draw [->] (z7) -- (2.75,-1.5);
		\draw (2.75,-1.5) -- (z6);
		\draw [->] (z2) -- (1.75,-2.5);
		\draw (1.75,-2.5) -- (z4);		
		\draw [->] (z7) -- (1.75,-1.5);
		\draw (1.75,-1.5) -- (z4);	
		\draw [->] (z7) -- (2.25,-1.5);
		\draw (2.25,-1.5) -- (z5);	
		\draw [->] (z4) -- (2,-2);
		\draw (2,-2) -- (z5);	
		\draw [->>] (z7) -- (1.25,-1.5);
		\draw (1.25,-1.5) -- (z3);	
		\draw [->] (z3) -- (1,-2);
		\draw (1,-2) -- (z4);
		\draw [->] (z1) -- (1.25,-3);
		\draw (1.25,-3) -- (z3);


					
		
		
		\node[vertex] (w1) at (6,-4)   { };
		\node[vertex] (w2) at (6,-3)   { };
		\node[vertex, fill=white, draw] (w3) at (4.5,-2)   { };
		\node[vertex, fill=white, draw] (w4) at (5.5,-2)   { };
		\node[vertex, fill=white, draw] (w5) at (6.5,-2)   { };
		\node[vertex] (w6) at (7.5,-2)   { };
		\node[vertex, fill=white, draw] (w7) at (6,-1)   { };	

		\draw [->]  (w1) -- (6,-3.5);
		\draw (6,-3.5) -- (w2);
		\draw [->] (w1) -- (6.75,-3);
		\draw (6.75,-3) -- (w6);
		\draw [->] (w6) -- (7,-2);
		\draw (7,-2) -- (w5);
		\draw [->] (w2) -- (6.25,-2.5);
		\draw (6.25,-2.5) -- (w5);
		\draw [->] (w7) -- (6.75,-1.5);
		\draw (6.75,-1.5) -- (w6);
		\draw [->] (w2) -- (5.75,-2.5);
		\draw (5.75,-2.5) -- (w4);		
		\draw [->] (w7) -- (5.75,-1.5);
		\draw (5.75,-1.5) -- (w4);	
		\draw [->] (w7) -- (6.25,-1.5);
		\draw (6.25,-1.5) -- (w5);	
		\draw [->] (w4) -- (6,-2);
		\draw (6,-2) -- (w5);	
		\draw [->] (w7) -- (5.25,-1.5);
		\draw (5.25,-1.5) -- (w3);	
		\draw [->] (w3) -- (5,-2);
		\draw (5,-2) -- (w4);
		\draw [->] (w1) -- (5.25,-3);
		\draw (5.25,-3) -- (w3);



				
		    	
		
				
	\end{tikzpicture}

\end{center}

\medskip
\noindent
{\it Case} 1.2.2: The orientation of the edge chosen in Case 1.2.1 is reversed (solid arrow) and one consequence is derived (double arrow). 

\begin{center}
	\begin{tikzpicture}
  		[scale=1,auto=left]
		
		
		\node[vertex] (n1) at (0,0)   { };
		\node[vertex] (n2) at (0,1)   { };
		\node[vertex] (n3) at (-1.5,2)   { };
		\node[vertex] (n4) at (-0.5,2)   { };
		\node[vertex] (n5) at (0.5,2)   { };
		\node[vertex] (n6) at (1.5,2)   { };
		\node[vertex] (n7) at (0,3)   { };		


		\draw [->]  (n1) -- (0,0.5);
		\draw (0,0.5) -- (n2);
		\draw [->]  (n1) -- (0.75,1);
		\draw (0.75,1) -- (n6);
		\draw [-latex] (n5) -- (0.25,1.5);
		\draw (0.25,1.5) -- (n2);
		\draw [->>] (n5) -- (1,2);
		\draw (1,2) -- (n6);


	
		\foreach \from/\to in {n1/n3, n2/n4, n7/n3, n7/n4, n7/n5, n7/n6, n3/n4, n4/n5}
    	\draw (\from) -- (\to);
		
    	
		
				
	\end{tikzpicture}

\end{center}

\medskip
\noindent
{\it Case} 1.2.2.1: One more edge is oriented (solid arrow) leading to a contradiction. 

\begin{center}
	\begin{tikzpicture}
  		[scale=1,auto=left]
		
		\node[vertex, fill=white, draw] (n1) at (0,0)   { };
		\node[vertex] (n2) at (0,1)   { };
		\node[vertex, fill=white, draw] (n3) at (-1.5,2)   { };
		\node[vertex] (n4) at (-0.5,2)   { };
		\node[vertex] (n5) at (0.5,2)   { };
		\node[vertex, fill=white, draw] (n6) at (1.5,2)   { };
		\node[vertex, fill=white, draw] (n7) at (0,3)   { };		



		\draw [->]  (n1) -- (0,0.5);
		\draw (0,0.5) -- (n2);
		\draw [->] (n1) -- (0.75,1);
		\draw (0.75,1) -- (n6);
		\draw [->] (n5) -- (1,2);
		\draw (1,2) -- (n6);
		\draw [->] (n5) -- (0.25,1.5);
		\draw (0.25,1.5) -- (n2);
		\draw [-latex] (n6) -- (0.75,2.5);
		\draw (0.75,2.5) -- (n7);
		\draw [->>] (n1) -- (-0.75,1);
		\draw (-0.75,1) -- (n3);	
		\draw [->>] (n3) -- (-0.75,2.5);
		\draw (-0.75,2.5) -- (n7);


					
		\foreach \from/\to in {n7/n5, n2/n4, n4/n5, n4/n7, n3/n4}
    	\draw (\from) -- (\to);
		
    	
		

		
		\node[vertex] (x1) at (4,0)   { };
		\node[vertex] (x2) at (4,1)   { };
		\node[vertex] (x3) at (2.5,2)   { };
		\node[vertex] (x4) at (3.5,2)   { };
		\node[vertex, fill=white, draw] (x5) at (4.5,2)   { };
		\node[vertex, fill=white, draw] (x6) at (5.5,2)   { };
		\node[vertex, fill=white, draw] (x7) at (4,3)   { };	

		\draw [->]  (x1) -- (4,0.5);
		\draw (4,0.5) -- (x2);
		\draw [->] (x1) -- (4.75,1);
		\draw (4.75,1) -- (x6);
		\draw [->] (x5) -- (5,2);
		\draw (5,2) -- (x6);
		\draw [->] (x5) -- (4.25,1.5);
		\draw (4.25,1.5) -- (x2);
		\draw [->] (x6) -- (4.75,2.5);
		\draw (4.75,2.5) -- (x7);
		\draw [->>] (x5) -- (4.25,2.5);
		\draw (4.25,2.5) -- (x7);	
		\draw [->] (x1) -- (3.25,1);
		\draw (3.25,1) -- (x3);	
		\draw [->] (x3) -- (3.25,2.5);
		\draw (3.25,2.5) -- (x7);
		


			
		\foreach \from/\to in {x3/x4, x1/x3, x3/x7, x2/x4, x4/x5, x4/x7}
    	\draw (\from) -- (\to);



		\node[vertex] (y1) at (8,0)   { };
		\node[vertex] (y2) at (8,1)   { };
		\node[vertex] (y3) at (6.5,2)   { };
		\node[vertex, fill=white, draw] (y4) at (7.5,2)   { };
		\node[vertex, fill=white, draw] (y5) at (8.5,2)   { };
		\node[vertex, fill=white, draw] (y6) at (9.5,2)   { };
		\node[vertex, fill=white, draw] (y7) at (8,3)   { };	

		\draw [->]  (y1) -- (8,0.5);
		\draw (8,0.5) -- (y2);
		\draw [->] (y1) -- (8.75,1);
		\draw (8.75,1) -- (y6);
		\draw [->] (y5) -- (9,2);
		\draw (9,2) -- (y6);
		\draw [->] (y5) -- (8.25,1.5);
		\draw (8.25,1.5) -- (y2);
		\draw [->] (y6) -- (8.75,2.5);
		\draw (8.75,2.5) -- (y7);
		\draw [->>] (y4) -- (7.75,2.5);
		\draw (7.75,2.5) -- (y7);	
		\draw [->] (y5) -- (8.25,2.5);
		\draw (8.25,2.5) -- (y7);	
		\draw [->>] (y5) -- (8,2);
		\draw (8,2) -- (y4);	
		\draw [->] (y1) -- (7.25,1);
		\draw (7.25,1) -- (y3);
		\draw [->] (y3) -- (7.25,2.5);
		\draw (7.25,2.5) -- (y7);

		

		\foreach \from/\to in {y2/y4, y3/y4}
    	\draw (\from) -- (\to);





		\node[vertex] (z1) at (0,-4)   { };
		\node[vertex, fill=white, draw] (z2) at (0,-3)   { };
		\node[vertex] (z3) at (-1.5,-2)   { };
		\node[vertex, fill=white, draw] (z4) at (-0.5,-2)   { };
		\node[vertex, fill=white, draw] (z5) at (0.5,-2)   { };
		\node[vertex] (z6) at (1.5,-2)   { };
		\node[vertex, fill=white, draw] (z7) at (0,-1)   { };	
		
		\draw [->]  (z1) -- (0,-3.5);
		\draw (0,-3.5) -- (z2);
		\draw [->] (z1) -- (0.75,-3);
		\draw (0.75,-3) -- (z6);
		\draw [->] (z5) -- (1,-2);
		\draw (1,-2) -- (z6);
		\draw [->] (z5) -- (0.25,-2.5);
		\draw (0.25,-2.5) -- (z2);
		\draw [->] (z6) -- (0.75,-1.5);
		\draw (0.75,-1.5) -- (z7);
		\draw [->] (z1) -- (-0.75,-3);
		\draw (-0.75,-3) -- (z3);	
		\draw [->] (z3) -- (-0.75,-1.5);
		\draw (-0.75,-1.5) -- (z7);
		\draw [->>] (z4) -- (-0.25,-2.5);
		\draw (-0.25,-2.5) -- (z2);
		\draw [->] (z5) -- (0,-2);
		\draw (0,-2) -- (z4);
		\draw [->] (z5) -- (0.25,-1.5);
		\draw (0.25,-1.5) -- (z7);
		\draw [->] (z4) -- (-0.25,-1.5);
		\draw (-0.25,-1.5) -- (z7);




		\foreach \from/\to in {z3/z4}
    	\draw (\from) -- (\to);







		\node[vertex] (w1) at (4,-4)   { };
		\node[vertex] (w2) at (4,-3)   { };
		\node[vertex, fill=white, draw] (w3) at (2.5,-2)   { };
		\node[vertex, fill=white, draw] (w4) at (3.5,-2)   { };
		\node[vertex, fill=white, draw] (w5) at (4.5,-2)   { };
		\node[vertex] (w6) at (5.5,-2)   { };
		\node[vertex, fill=white, draw] (w7) at (4,-1)   { };    	
		
		\draw [->]  (w1) -- (4,-3.5);
		\draw (4,-3.5) -- (w2);
		\draw [->] (w1) -- (4.75,-3);
		\draw (4.75,-3) -- (w6);
		\draw [->] (w5) -- (5,-2);
		\draw (5,-2) -- (w6);
		\draw [->] (w5) -- (4.25,-2.5);
		\draw (4.25,-2.5) -- (w2);
		\draw [->] (w6) -- (4.75,-1.5);
		\draw (4.75,-1.5) -- (w7);
		\draw [->] (w5) -- (4.25,-1.5);
		\draw (4.25,-1.5) -- (w7);	
		\draw [->] (w1) -- (3.25,-3);
		\draw (3.25,-3) -- (w3);	
		\draw [->] (w3) -- (3.25,-1.5);
		\draw (3.25,-1.5) -- (w7);
		\draw [->>] (w3) -- (3,-2);
		\draw (3,-2) -- (w4);
		\draw [->] (w4) -- (3.75,-1.5);
		\draw (3.75,-1.5) -- (w7);	
		\draw [->] (w5) -- (4,-2);
		\draw (4,-2) -- (w4);	
		\draw [->] (w4) -- (3.75,-2.5);
		\draw (3.75,-2.5) -- (w2);






		\node[vertex, fill=white, draw] (v1) at (8,-4)   { };
		\node[vertex, fill=white, draw] (v2) at (8,-3)   { };
		\node[vertex, fill=white, draw] (v3) at (6.5,-2)   { };
		\node[vertex, fill=white, draw] (v4) at (7.5,-2)   { };
		\node[vertex] (v5) at (8.5,-2)   { };
		\node[vertex] (v6) at (9.5,-2)   { };
		\node[vertex] (v7) at (8,-1)   { };				


		\draw [->]  (v1) -- (8,-3.5);
		\draw (8,-3.5) -- (v2);
		\draw [->] (v1) -- (8.75,-3);
		\draw (8.75,-3) -- (v6);
		\draw [->] (v5) -- (9,-2);
		\draw (9,-2) -- (v6);
		\draw [->] (v5) -- (8.25,-2.5);
		\draw (8.25,-2.5) -- (v2);
		\draw [->] (v6) -- (8.75,-1.5);
		\draw (8.75,-1.5) -- (v7);
		\draw [->] (v5) -- (8.25,-1.5);
		\draw (8.25,-1.5) -- (v7);	
		\draw [->] (v1) -- (7.25,-3);
		\draw (7.25,-3) -- (v3);	
		\draw [->] (v3) -- (7.25,-1.5);
		\draw (7.25,-1.5) -- (v7);
		\draw [->] (v3) -- (7,-2);
		\draw (7,-2) -- (v4);
		\draw [->] (v4) -- (7.75,-1.5);
		\draw (7.75,-1.5) -- (v7);	
		\draw [->] (v5) -- (8,-2);
		\draw (8,-2) -- (v4);	
		\draw [->] (v4) -- (7.75,-2.5);
		\draw (7.75,-2.5) -- (v2);

					
	\end{tikzpicture}

\end{center}

\medskip
\noindent
{\it Case} 1.2.2.2: The orientation of the edge chosen in Case 1.2.2.1 is reversed. 

\begin{center}
	\begin{tikzpicture}
  		[scale=1,auto=left]
		
		\node[vertex] (n1) at (0,0)   { };
		\node[vertex] (n2) at (0,1)   { };
		\node[vertex] (n3) at (-1.5,2)   { };
		\node[vertex] (n4) at (-0.5,2)   { };
		\node[vertex] (n5) at (0.5,2)   { };
		\node[vertex] (n6) at (1.5,2)   { };
		\node[vertex] (n7) at (0,3)   { };		



		\draw [->]  (n1) -- (0,0.5);
		\draw (0,0.5) -- (n2);
		\draw [->] (n1) -- (0.75,1);
		\draw (0.75,1) -- (n6);
		\draw [->] (n5) -- (1,2);
		\draw (1,2) -- (n6);
		\draw [->] (n5) -- (0.25,1.5);
		\draw (0.25,1.5) -- (n2);
		\draw [-latex] (n7) -- (0.75,2.5);
		\draw (0.75,2.5) -- (n6);
		


					
		\foreach \from/\to in {n1/n3, n3/n7, n7/n5, n2/n4, n4/n5, n4/n7, n3/n4}
    	\draw (\from) -- (\to);


		    	
		
				
	\end{tikzpicture}

\end{center}

\medskip
\noindent
{\it Case} 1.2.2.2.1: One more edge is oriented (solid arrow) leading to a contradiction.

\begin{center}
	\begin{tikzpicture}
  		[scale=1,auto=left]
		
		\node[vertex] (n1) at (0,0)   { };
		\node[vertex, fill=white, draw] (n2) at (0,1)   { };
		\node[vertex] (n3) at (-1.5,2)   { };
		\node[vertex, fill=white, draw] (n4) at (-0.5,2)   { };
		\node[vertex, fill=white, draw] (n5) at (0.5,2)   { };
		\node[vertex] (n6) at (1.5,2)   { };
		\node[vertex, fill=white, draw] (n7) at (0,3)   { };		



		\draw [->]  (n1) -- (0,0.5);
		\draw (0,0.5) -- (n2);
		\draw [->] (n1) -- (0.75,1);
		\draw (0.75,1) -- (n6);
		\draw [->] (n5) -- (1,2);
		\draw (1,2) -- (n6);
		\draw [->] (n5) -- (0.25,1.5);
		\draw (0.25,1.5) -- (n2);
		\draw [->] (n7) -- (0.75,2.5);
		\draw (0.75,2.5) -- (n6);
		\draw [->>] (n5) -- (0.25,2.5);
		\draw (0.25,2.5) -- (n7);	
		\draw [-latex] (n2) -- (-0.25,1.5);
		\draw (-0.25,1.5) -- (n4);
		\draw [->>] (n7) -- (-0.25,2.5);
		\draw (-0.25,2.5) -- (n4);	


					
		\foreach \from/\to in {n5/n4, n3/n7, n3/n4, n1/n3}
    	\draw (\from) -- (\to);
		
    	
		

		
		\node[vertex] (x1) at (4,0)   { };
		\node[vertex] (x2) at (4,1)   { };
		\node[vertex] (x3) at (2.5,2)   { };
		\node[vertex, fill=white, draw] (x4) at (3.5,2)   { };
		\node[vertex, fill=white, draw] (x5) at (4.5,2)   { };
		\node[vertex, fill=white, draw] (x6) at (5.5,2)   { };
		\node[vertex, fill=white, draw] (x7) at (4,3)   { };	

		\draw [->]  (x1) -- (4,0.5);
		\draw (4,0.5) -- (x2);
		\draw [->] (x1) -- (4.75,1);
		\draw (4.75,1) -- (x6);
		\draw [->] (x5) -- (5,2);
		\draw (5,2) -- (x6);
		\draw [->] (x5) -- (4.25,1.5);
		\draw (4.25,1.5) -- (x2);
		\draw [->] (x7) -- (4.75,2.5);
		\draw (4.75,2.5) -- (x6);
		\draw [->] (x5) -- (4.25,2.5);
		\draw (4.25,2.5) -- (x7);	
		\draw [->>] (x5) -- (4,2);
		\draw (4,2) -- (x4);	
		\draw [->] (x7) -- (3.75,2.5);
		\draw (3.75,2.5) -- (x4);
		\draw [->] (x2) -- (3.75,1.5);
		\draw (3.75,1.5) -- (x4);


			
		\foreach \from/\to in {x3/x4, x1/x3, x3/x7, x1/x3, x3/x7}
    	\draw (\from) -- (\to);



		\node[vertex, fill=white, draw] (y1) at (8,0)   { };
		\node[vertex, fill=white, draw] (y2) at (8,1)   { };
		\node[vertex, fill=white, draw] (y3) at (6.5,2)   { };
		\node[vertex, fill=white, draw] (y4) at (7.5,2)   { };
		\node[vertex] (y5) at (8.5,2)   { };
		\node[vertex] (y6) at (9.5,2)   { };
		\node[vertex] (y7) at (8,3)   { };	

		\draw [->]  (y1) -- (8,0.5);
		\draw (8,0.5) -- (y2);
		\draw [->] (y1) -- (8.75,1);
		\draw (8.75,1) -- (y6);
		\draw [->] (y5) -- (9,2);
		\draw (9,2) -- (y6);
		\draw [->] (y5) -- (8.25,1.5);
		\draw (8.25,1.5) -- (y2);
		\draw [->] (y7) -- (8.75,2.5);
		\draw (8.75,2.5) -- (y6);
		\draw [->] (y7) -- (7.75,2.5);
		\draw (7.75,2.5) -- (y4);	
		\draw [->] (y5) -- (8.25,2.5);
		\draw (8.25,2.5) -- (y7);	
		\draw [->] (y5) -- (8,2);
		\draw (8,2) -- (y4);	
		\draw [->] (y2) -- (7.75,1.5);
		\draw (7.75,1.5) -- (y4);	
		\draw [->>] (y3) -- (7,2);
		\draw (7,2) -- (y4);
		\draw [->>] (y1) -- (7.25,1);
		\draw (7.25,1) -- (y3);

		

		\foreach \from/\to in {y3/y7}
    	\draw (\from) -- (\to);

			
		    	
						
		\node[vertex, fill=white, draw] (z1) at (2,-4)   { };
		\node[vertex] (z2) at (2,-3)   { };
		\node[vertex, fill=white, draw] (z3) at (0.5,-2)   { };
		\node[vertex] (z4) at (1.5,-2)   { };
		\node[vertex] (z5) at (2.5,-2)   { };
		\node[vertex, fill=white, draw] (z6) at (3.5,-2)   { };
		\node[vertex, fill=white, draw] (z7) at (2,-1)   { };		



		\draw [->]  (z1) -- (2,-3.5);
		\draw (2,-3.5) -- (z2);
		\draw [->] (z1) -- (2.75,-3);
		\draw (2.75,-3) -- (z6);
		\draw [->] (z5) -- (3,-2);
		\draw (3,-2) -- (z6);
		\draw [->] (z5) -- (2.25,-2.5);
		\draw (2.25,-2.5) -- (z2);
		\draw [->] (z7) -- (2.75,-1.5);
		\draw (2.75,-1.5) -- (z6);
		\draw [->] (z2) -- (1.75,-2.5);
		\draw (1.75,-2.5) -- (z4);		
		\draw [->] (z7) -- (1.75,-1.5);
		\draw (1.75,-1.5) -- (z4);	
		\draw [->] (z5) -- (2.25,-1.5);
		\draw (2.25,-1.5) -- (z7);	
		\draw [->] (z5) -- (2,-2);
		\draw (2,-2) -- (z4);	
		\draw [->>] (z7) -- (1.25,-1.5);
		\draw (1.25,-1.5) -- (z3);	
		\draw [->] (z3) -- (1,-2);
		\draw (1,-2) -- (z4);
		\draw [->] (z1) -- (1.25,-3);
		\draw (1.25,-3) -- (z3);


					
		
		
		\node[vertex] (w1) at (6,-4)   { };
		\node[vertex] (w2) at (6,-3)   { };
		\node[vertex, fill=white, draw] (w3) at (4.5,-2)   { };
		\node[vertex, fill=white, draw] (w4) at (5.5,-2)   { };
		\node[vertex, fill=white, draw] (w5) at (6.5,-2)   { };
		\node[vertex] (w6) at (7.5,-2)   { };
		\node[vertex, fill=white, draw] (w7) at (6,-1)   { };	

		\draw [->]  (w1) -- (6,-3.5);
		\draw (6,-3.5) -- (w2);
		\draw [->] (w1) -- (6.75,-3);
		\draw (6.75,-3) -- (w6);
		\draw [->] (w5) -- (7,-2);
		\draw (7,-2) -- (w6);
		\draw [->] (w5) -- (6.25,-2.5);
		\draw (6.25,-2.5) -- (w2);
		\draw [->] (w7) -- (6.75,-1.5);
		\draw (6.75,-1.5) -- (w6);
		\draw [->] (w2) -- (5.75,-2.5);
		\draw (5.75,-2.5) -- (w4);		
		\draw [->] (w7) -- (5.75,-1.5);
		\draw (5.75,-1.5) -- (w4);	
		\draw [->] (w5) -- (6.25,-1.5);
		\draw (6.25,-1.5) -- (w7);	
		\draw [->] (w5) -- (6,-2);
		\draw (6,-2) -- (w4);	
		\draw [->] (w7) -- (5.25,-1.5);
		\draw (5.25,-1.5) -- (w3);	
		\draw [->] (w3) -- (5,-2);
		\draw (5,-2) -- (w4);
		\draw [->] (w1) -- (5.25,-3);
		\draw (5.25,-3) -- (w3);



				
		    	
		
				
	\end{tikzpicture}

\end{center}

\medskip
\noindent
{\it Case} 1.2.2.2.2: The orientation of the edge chosen in Case 1.2.2.2.1 is reversed.

\begin{center}
	\begin{tikzpicture}
  		[scale=1,auto=left]
		
		\node[vertex] (n1) at (0,0)   { };
		\node[vertex] (n2) at (0,1)   { };
		\node[vertex] (n3) at (-1.5,2)   { };
		\node[vertex] (n4) at (-0.5,2)   { };
		\node[vertex] (n5) at (0.5,2)   { };
		\node[vertex] (n6) at (1.5,2)   { };
		\node[vertex] (n7) at (0,3)   { };		



		\draw [->]  (n1) -- (0,0.5);
		\draw (0,0.5) -- (n2);
		\draw [->] (n1) -- (0.75,1);
		\draw (0.75,1) -- (n6);
		\draw [->] (n5) -- (1,2);
		\draw (1,2) -- (n6);
		\draw [->] (n5) -- (0.25,1.5);
		\draw (0.25,1.5) -- (n2);
		\draw [->] (n7) -- (0.75,2.5);
		\draw (0.75,2.5) -- (n6);
		\draw [-latex] (n4) -- (-0.25,1.5);
		\draw (-0.25,1.5) -- (n2);


					
		\foreach \from/\to in {n1/n3, n3/n7, n7/n5, n4/n5, n4/n7, n3/n4}
    	\draw (\from) -- (\to);


		    	
		
				
	\end{tikzpicture}

\end{center}

\medskip
\noindent
{\it Case} 1.2.2.2.2.1: One more edge is oriented (solid arrow) leading to a contradiction.

\begin{center}
	\begin{tikzpicture}
  		[scale=1,auto=left]
		
		\node[vertex] (n1) at (0,0)   { };
		\node[vertex, fill=white, draw] (n2) at (0,1)   { };
		\node[vertex] (n3) at (-1.5,2)   { };
		\node[vertex, fill=white, draw] (n4) at (-0.5,2)   { };
		\node[vertex, fill=white, draw] (n5) at (0.5,2)   { };
		\node[vertex] (n6) at (1.5,2)   { };
		\node[vertex, fill=white, draw] (n7) at (0,3)   { };		



		\draw [->]  (n1) -- (0,0.5);
		\draw (0,0.5) -- (n2);
		\draw [->] (n1) -- (0.75,1);
		\draw (0.75,1) -- (n6);
		\draw [->] (n5) -- (1,2);
		\draw (1,2) -- (n6);
		\draw [->] (n5) -- (0.25,1.5);
		\draw (0.25,1.5) -- (n2);
		\draw [->] (n7) -- (0.75,2.5);
		\draw (0.75,2.5) -- (n6);
		\draw [->>] (n7) -- (0.25,2.5);
		\draw (0.25,2.5) -- (n5);	
		\draw [->] (n4) -- (-0.25,1.5);
		\draw (-0.25,1.5) -- (n2);
		\draw [-latex] (n7) -- (-0.25,2.5);
		\draw (-0.25,2.5) -- (n4);	


					
		\foreach \from/\to in {n5/n4, n3/n7, n3/n4, n1/n3}
    	\draw (\from) -- (\to);
		
    	
		

		
		\node[vertex] (x1) at (4,0)   { };
		\node[vertex] (x2) at (4,1)   { };
		\node[vertex] (x3) at (2.5,2)   { };
		\node[vertex, fill=white, draw] (x4) at (3.5,2)   { };
		\node[vertex, fill=white, draw] (x5) at (4.5,2)   { };
		\node[vertex, fill=white, draw] (x6) at (5.5,2)   { };
		\node[vertex, fill=white, draw] (x7) at (4,3)   { };	

		\draw [->]  (x1) -- (4,0.5);
		\draw (4,0.5) -- (x2);
		\draw [->] (x1) -- (4.75,1);
		\draw (4.75,1) -- (x6);
		\draw [->] (x5) -- (5,2);
		\draw (5,2) -- (x6);
		\draw [->] (x5) -- (4.25,1.5);
		\draw (4.25,1.5) -- (x2);
		\draw [->] (x7) -- (4.75,2.5);
		\draw (4.75,2.5) -- (x6);
		\draw [->] (x7) -- (4.25,2.5);
		\draw (4.25,2.5) -- (x5);	
		\draw [->>] (x5) -- (4,2);
		\draw (4,2) -- (x4);	
		\draw [->] (x7) -- (3.75,2.5);
		\draw (3.75,2.5) -- (x4);
		\draw [->] (x4) -- (3.75,1.5);
		\draw (3.75,1.5) -- (x2);


			
		\foreach \from/\to in {x3/x4, x1/x3, x3/x7, x1/x3, x3/x7}
    	\draw (\from) -- (\to);



		\node[vertex] (y1) at (8,0)   { };
		\node[vertex] (y2) at (8,1)   { };
		\node[vertex, fill=white, draw] (y3) at (6.5,2)   { };
		\node[vertex, fill=white, draw] (y4) at (7.5,2)   { };
		\node[vertex, fill=white, draw] (y5) at (8.5,2)   { };
		\node[vertex] (y6) at (9.5,2)   { };
		\node[vertex, fill=white, draw] (y7) at (8,3)   { };	

		\draw [->]  (y1) -- (8,0.5);
		\draw (8,0.5) -- (y2);
		\draw [->] (y1) -- (8.75,1);
		\draw (8.75,1) -- (y6);
		\draw [->] (y5) -- (9,2);
		\draw (9,2) -- (y6);
		\draw [->] (y5) -- (8.25,1.5);
		\draw (8.25,1.5) -- (y2);
		\draw [->] (y7) -- (8.75,2.5);
		\draw (8.75,2.5) -- (y6);
		\draw [->] (y7) -- (7.75,2.5);
		\draw (7.75,2.5) -- (y4);	
		\draw [->] (y7) -- (8.25,2.5);
		\draw (8.25,2.5) -- (y5);	
		\draw [->] (y5) -- (8,2);
		\draw (8,2) -- (y4);	
		\draw [->] (y4) -- (7.75,1.5);
		\draw (7.75,1.5) -- (y2);	
		\draw [->>] (y3) -- (7,2);
		\draw (7,2) -- (y4);
		\draw [->>] (y7) -- (7.25,2.5);
		\draw (7.25,2.5) -- (y3);

		

		\foreach \from/\to in {y1/y3}
    	\draw (\from) -- (\to);

			
		    	
						
		\node[vertex, fill=white, draw] (z1) at (2,-4)   { };
		\node[vertex] (z2) at (2,-3)   { };
		\node[vertex, fill=white, draw] (z3) at (0.5,-2)   { };
		\node[vertex] (z4) at (1.5,-2)   { };
		\node[vertex] (z5) at (2.5,-2)   { };
		\node[vertex, fill=white, draw] (z6) at (3.5,-2)   { };
		\node[vertex, fill=white, draw] (z7) at (2,-1)   { };		



		\draw [->]  (z1) -- (2,-3.5);
		\draw (2,-3.5) -- (z2);
		\draw [->] (z1) -- (2.75,-3);
		\draw (2.75,-3) -- (z6);
		\draw [->] (z5) -- (3,-2);
		\draw (3,-2) -- (z6);
		\draw [->] (z5) -- (2.25,-2.5);
		\draw (2.25,-2.5) -- (z2);
		\draw [->] (z7) -- (2.75,-1.5);
		\draw (2.75,-1.5) -- (z6);
		\draw [->] (z4) -- (1.75,-2.5);
		\draw (1.75,-2.5) -- (z2);		
		\draw [->] (z7) -- (1.75,-1.5);
		\draw (1.75,-1.5) -- (z4);	
		\draw [->] (z7) -- (2.25,-1.5);
		\draw (2.25,-1.5) -- (z5);	
		\draw [->] (z5) -- (2,-2);
		\draw (2,-2) -- (z4);	
		\draw [->] (z7) -- (1.25,-1.5);
		\draw (1.25,-1.5) -- (z3);	
		\draw [->] (z3) -- (1,-2);
		\draw (1,-2) -- (z4);
		\draw [->>] (z1) -- (1.25,-3);
		\draw (1.25,-3) -- (z3);


					
		
		
		\node[vertex, fill=white, draw] (w1) at (6,-4)   { };
		\node[vertex, fill=white, draw] (w2) at (6,-3)   { };
		\node[vertex, fill=white, draw] (w3) at (4.5,-2)   { };
		\node[vertex, fill=white, draw] (w4) at (5.5,-2)   { };
		\node[vertex] (w5) at (6.5,-2)   { };
		\node[vertex] (w6) at (7.5,-2)   { };
		\node[vertex] (w7) at (6,-1)   { };	

		\draw [->]  (w1) -- (6,-3.5);
		\draw (6,-3.5) -- (w2);
		\draw [->] (w1) -- (6.75,-3);
		\draw (6.75,-3) -- (w6);
		\draw [->] (w5) -- (7,-2);
		\draw (7,-2) -- (w6);
		\draw [->] (w5) -- (6.25,-2.5);
		\draw (6.25,-2.5) -- (w2);
		\draw [->] (w7) -- (6.75,-1.5);
		\draw (6.75,-1.5) -- (w6);
		\draw [->] (w4) -- (5.75,-2.5);
		\draw (5.75,-2.5) -- (w2);		
		\draw [->] (w7) -- (5.75,-1.5);
		\draw (5.75,-1.5) -- (w4);	
		\draw [->] (w7) -- (6.25,-1.5);
		\draw (6.25,-1.5) -- (w5);	
		\draw [->] (w5) -- (6,-2);
		\draw (6,-2) -- (w4);	
		\draw [->] (w7) -- (5.25,-1.5);
		\draw (5.25,-1.5) -- (w3);	
		\draw [->] (w3) -- (5,-2);
		\draw (5,-2) -- (w4);
		\draw [->] (w1) -- (5.25,-3);
		\draw (5.25,-3) -- (w3);



				
		    	
		
				
	\end{tikzpicture}

\end{center}

\medskip
\noindent
{\it Case} 1.2.2.2.2.2: The orientation of the edge chosen in Case 1.2.2.2.2.1 is reversed, which leads to a contradiction again. 
This completes the analysis of Case 1.

\begin{center}
	\begin{tikzpicture}
  		[scale=1,auto=left]
		
		\node[vertex] (n1) at (0,0)   { };
		\node[vertex, fill=white, draw] (n2) at (0,1)   { };
		\node[vertex] (n3) at (-1.5,2)   { };
		\node[vertex, fill=white, draw] (n4) at (-0.5,2)   { };
		\node[vertex, fill=white, draw] (n5) at (0.5,2)   { };
		\node[vertex] (n6) at (1.5,2)   { };
		\node[vertex, fill=white, draw] (n7) at (0,3)   { };		



		\draw [->]  (n1) -- (0,0.5);
		\draw (0,0.5) -- (n2);
		\draw [->] (n1) -- (0.75,1);
		\draw (0.75,1) -- (n6);
		\draw [->] (n5) -- (1,2);
		\draw (1,2) -- (n6);
		\draw [->] (n5) -- (0.25,1.5);
		\draw (0.25,1.5) -- (n2);
		\draw [->] (n7) -- (0.75,2.5);
		\draw (0.75,2.5) -- (n6);
		\draw [->>] (n5) -- (0.25,2.5);
		\draw (0.25,2.5) -- (n7);	
		\draw [->] (n4) -- (-0.25,1.5);
		\draw (-0.25,1.5) -- (n2);
		\draw [-latex] (n4) -- (-0.25,2.5);
		\draw (-0.25,2.5) -- (n7);	


					
		\foreach \from/\to in {n5/n4, n3/n7, n3/n4, n1/n3}
    	\draw (\from) -- (\to);
		
    	
		

		
		\node[vertex] (x1) at (4,0)   { };
		\node[vertex] (x2) at (4,1)   { };
		\node[vertex] (x3) at (2.5,2)   { };
		\node[vertex, fill=white, draw] (x4) at (3.5,2)   { };
		\node[vertex, fill=white, draw] (x5) at (4.5,2)   { };
		\node[vertex, fill=white, draw] (x6) at (5.5,2)   { };
		\node[vertex, fill=white, draw] (x7) at (4,3)   { };	

		\draw [->]  (x1) -- (4,0.5);
		\draw (4,0.5) -- (x2);
		\draw [->] (x1) -- (4.75,1);
		\draw (4.75,1) -- (x6);
		\draw [->] (x5) -- (5,2);
		\draw (5,2) -- (x6);
		\draw [->] (x5) -- (4.25,1.5);
		\draw (4.25,1.5) -- (x2);
		\draw [->] (x7) -- (4.75,2.5);
		\draw (4.75,2.5) -- (x6);
		\draw [->] (x5) -- (4.25,2.5);
		\draw (4.25,2.5) -- (x7);	
		\draw [->>] (x4) -- (4,2);
		\draw (4,2) -- (x5);	
		\draw [->] (x4) -- (3.75,2.5);
		\draw (3.75,2.5) -- (x7);
		\draw [->] (x4) -- (3.75,1.5);
		\draw (3.75,1.5) -- (x2);


			
		\foreach \from/\to in {x3/x4, x1/x3, x3/x7, x1/x3, x3/x7}
    	\draw (\from) -- (\to);



		\node[vertex] (y1) at (8,0)   { };
		\node[vertex] (y2) at (8,1)   { };
		\node[vertex, fill=white, draw] (y3) at (6.5,2)   { };
		\node[vertex, fill=white, draw] (y4) at (7.5,2)   { };
		\node[vertex, fill=white, draw] (y5) at (8.5,2)   { };
		\node[vertex] (y6) at (9.5,2)   { };
		\node[vertex, fill=white, draw] (y7) at (8,3)   { };	

		\draw [->]  (y1) -- (8,0.5);
		\draw (8,0.5) -- (y2);
		\draw [->] (y1) -- (8.75,1);
		\draw (8.75,1) -- (y6);
		\draw [->] (y5) -- (9,2);
		\draw (9,2) -- (y6);
		\draw [->] (y5) -- (8.25,1.5);
		\draw (8.25,1.5) -- (y2);
		\draw [->] (y7) -- (8.75,2.5);
		\draw (8.75,2.5) -- (y6);
		\draw [->] (y4) -- (7.75,2.5);
		\draw (7.75,2.5) -- (y7);	
		\draw [->] (y5) -- (8.25,2.5);
		\draw (8.25,2.5) -- (y7);	
		\draw [->] (y4) -- (8,2);
		\draw (8,2) -- (y5);	
		\draw [->] (y4) -- (7.75,1.5);
		\draw (7.75,1.5) -- (y2);	
		\draw [->>] (y4) -- (7,2);
		\draw (7,2) -- (y3);
		\draw [->>] (y3) -- (7.25,2.5);
		\draw (7.25,2.5) -- (y7);

		

		\foreach \from/\to in {y1/y3}
    	\draw (\from) -- (\to);

			
		    	
						
		\node[vertex, fill=white, draw] (z1) at (2,-4)   { };
		\node[vertex] (z2) at (2,-3)   { };
		\node[vertex, fill=white, draw] (z3) at (0.5,-2)   { };
		\node[vertex] (z4) at (1.5,-2)   { };
		\node[vertex] (z5) at (2.5,-2)   { };
		\node[vertex, fill=white, draw] (z6) at (3.5,-2)   { };
		\node[vertex, fill=white, draw] (z7) at (2,-1)   { };		



		\draw [->]  (z1) -- (2,-3.5);
		\draw (2,-3.5) -- (z2);
		\draw [->] (z1) -- (2.75,-3);
		\draw (2.75,-3) -- (z6);
		\draw [->] (z5) -- (3,-2);
		\draw (3,-2) -- (z6);
		\draw [->] (z5) -- (2.25,-2.5);
		\draw (2.25,-2.5) -- (z2);
		\draw [->] (z7) -- (2.75,-1.5);
		\draw (2.75,-1.5) -- (z6);
		\draw [->] (z4) -- (1.75,-2.5);
		\draw (1.75,-2.5) -- (z2);		
		\draw [->] (z4) -- (1.75,-1.5);
		\draw (1.75,-1.5) -- (z7);	
		\draw [->] (z5) -- (2.25,-1.5);
		\draw (2.25,-1.5) -- (z7);	
		\draw [->] (z4) -- (2,-2);
		\draw (2,-2) -- (z5);	
		\draw [->] (z3) -- (1.25,-1.5);
		\draw (1.25,-1.5) -- (z7);	
		\draw [->] (z4) -- (1,-2);
		\draw (1,-2) -- (z3);
		\draw [->>] (z3) -- (1.25,-3);
		\draw (1.25,-3) -- (z1);


					
		
		
		\node[vertex, fill=white, draw] (w1) at (6,-4)   { };
		\node[vertex, fill=white, draw] (w2) at (6,-3)   { };
		\node[vertex, fill=white, draw] (w3) at (4.5,-2)   { };
		\node[vertex, fill=white, draw] (w4) at (5.5,-2)   { };
		\node[vertex] (w5) at (6.5,-2)   { };
		\node[vertex] (w6) at (7.5,-2)   { };
		\node[vertex] (w7) at (6,-1)   { };	

		\draw [->]  (w1) -- (6,-3.5);
		\draw (6,-3.5) -- (w2);
		\draw [->] (w1) -- (6.75,-3);
		\draw (6.75,-3) -- (w6);
		\draw [->] (w5) -- (7,-2);
		\draw (7,-2) -- (w6);
		\draw [->] (w5) -- (6.25,-2.5);
		\draw (6.25,-2.5) -- (w2);
		\draw [->] (w7) -- (6.75,-1.5);
		\draw (6.75,-1.5) -- (w6);
		\draw [->] (w4) -- (5.75,-2.5);
		\draw (5.75,-2.5) -- (w2);		
		\draw [->] (w4) -- (5.75,-1.5);
		\draw (5.75,-1.5) -- (w7);	
		\draw [->] (w5) -- (6.25,-1.5);
		\draw (6.25,-1.5) -- (w7);	
		\draw [->] (w4) -- (6,-2);
		\draw (6,-2) -- (w5);	
		\draw [->] (w3) -- (5.25,-1.5);
		\draw (5.25,-1.5) -- (w7);	
		\draw [->] (w4) -- (5,-2);
		\draw (5,-2) -- (w3);
		\draw [->] (w3) -- (5.25,-3);
		\draw (5.25,-3) -- (w1);

	\end{tikzpicture}

\end{center}


\medskip
\noindent
{\it Case} 2. In this case, we reverse the orientation of the edge chosen in Case 1 and complete the proof by symmetry,
i.e. by reversing the orientations obtained in Case 1.
\end{proof}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Asymptotic enumeration of word-representable graphs}
\label{sec:main}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Given a class $X$ of graphs, we write $X_n$ for the number of graphs in $X$ 
with vertex set $\{1,2,\ldots,n\}$, i.e. the number of {\it labelled} graphs in $X$. 
Following \cite{SpHerProp}, we call $X_n$ the {\it speed} of $X$. 

A class $X$ is {\it hereditary} if it is closed under taking induced subgraphs.
Alternatively, $X$ is hereditary if $G\in X$ implies $G-x\in X$ for any vertex 
$x\in V(G)$. Clearly, if $G$ is a word-representable graph and $w$ is a word 
representing $G$, then for any vertex $x\in V(G)$ the word obtained from $w$
by deleting all appearances of $x$ represents $G-x$. This observation leads
to the following obvious conclusion.

\begin{theorem}
The class of word-representable graphs is hereditary.
\end{theorem}

The speed of hereditary classes and their asymptotic structure have been extensively studied in the literature.
In particular, it is known that for every 
hereditary class $X$ different from the class of all finite graphs,
\begin{equation*}\label{eq:0}
\lim\limits_{n\to\infty}\frac{\log_2 X_n}{\binom{n}{2}}=1-\frac{1}{k(X)},
\end{equation*}
where $k(X)$ is a natural number, called the {\it index} of $X$. To define this notion 
let us denote by ${\cal E}_{i,j}$ the class of graphs whose vertices can be partitioned
into at most $i$ independent sets and $j$ cliques. In particular, ${\cal E}_{p,0}$
is the class of $p$-colorable graphs.
Then $k(X)$ is the largest $k$ such that $X$ contains ${\cal E}_{i,j}$ with $i+j=k$ for some $i$ and $j$. 
This result was obtained independently by Alekseev \cite{Ale92} and Bollob\'{a}s and Thomason  \cite{BT95,BT97}
and is known nowadays as the Alekseev-Bollob\'{a}s-Thomason Theorem (see e.g. \cite{ABT-theorem}).

Since $\binom{n}{2}$ is the minimum number of bits needed to represent an arbitrary 
$n$-vertex labeled graph and $\log_2 X_n$ is the minimum number of bits needed to represent an
$n$-vertex labeled graph in the class $X$,
the ratio $\log_2 X_n/{\binom{n}{2}}$ can be viewed as the coefficient of compressibility
for representing graphs in $X$ and its asymptotic value was called by Alekseev \cite{Ale82} 
the {\it entropy} of $X$.   

\medskip
We now apply the Alekseev-Bollob\'{a}s-Thomason Theorem in order to derive an asymptotic formula
for the number of word-representable graphs. We start with the number of $n$-vertex {\it labelled} 
graphs in this class, which we denote by $b_n$.  


\begin{theorem}\label{thm:bn} 
$$\lim_{n\to\infty}\frac{\log_2 b_n}{{n\choose 2}}=\frac{2}{3}.$$
\end{theorem}

\begin{proof}
By Theorem~\ref{thm:3col}, ${\cal E}_{3,0}$ is a subclass of the class of word-representable graphs
and hence its index is at least 3. In order to show that the index does not exceed 3, we observe that 
the graph $A$ represented in Figure~\ref{fig:A} belongs to all minimal classes of index 4,
and hence the family of word-representable graphs does not contain any of these minimal classes by 
Theorems~\ref{thm:semi-trans} and~\ref{thm:A}.
Therefore, the index of the class of word-representable graphs is precisely 3. 
\end{proof}

\medskip
We now proceed to the number of unlabelled  $n$-vertex word-representable graphs, which we denote by $a_n$.

\begin{theorem}\label{thm:an} 
$$\lim_{n\to\infty}\frac{\log_2 a_n}{{n\choose 2}}=\frac{2}{3}.$$
\end{theorem}
\begin{proof}
Clearly, $b_n\le n!a_n$ and $\log_2 n!\le\log_2 n^n =n\log_2 n$.
Therefore, 
$$\lim_{n\to\infty}\frac{\log_2 b_n}{{n\choose 2}}\le \lim_{n\to\infty}\frac{\log_2 (n!a_n)}{{n\choose 2}}=
\lim_{n\to\infty}\frac{\log_2 n! + \log_2 a_n}{{n\choose 2}}\le
\lim_{n\to\infty}\frac{n\log_2 n + \log_2 a_n}{{n\choose 2}}=\lim_{n\to\infty}\frac{\log_2 a_n}{{n\choose 2}}.$$

On the other hand, obviously $b_n\ge a_n$ and hence $\lim_{n\to\infty}\frac{\log_2 b_n}{{n\choose 2}}\ge\lim_{n\to\infty}\frac{\log_2 a_n}{{n\choose 2}}$.
Combining, we obtain $\lim_{n\to\infty}\frac{\log_2 b_n}{{n\choose 2}}=\lim_{n\to\infty}\frac{\log_2 a_n}{{n\choose 2}}$.
Together with Theorem~\ref{thm:bn}, this proves the result.
\end{proof}

\begin{corollary}\label{cor-main}
$$a_n=2^{\frac{n^2}{3}+o(n^2)}.$$
\end{corollary}


% \section{Concluding remark}

% A natural open problem is to better estimate the low term in the exponent of $2^{\frac{n^2}{3}+o(n^2)}$.
% However, our knowledge of word-representable graphs is still too limited to answer this question. 

\section{Acknowledgment}

The authors are grateful to the Edinburgh Mathematical Society for supporting 
the last authors' visit of the University of Strathclyde, during which parts of the presented results were obtained.
The last author also acknowledges support from DIMAP - the Center
for Discrete Mathematics and its Applications at the University of Warwick,
and from EPSRC, grant EP/I01795X/1. 

\begin{thebibliography}{25}

\bibitem{Ale82} 
{\sc V.E. Alekseev}, 
Hereditary classes and coding of graphs, 
{\it Probl. Cybernet}. 39 (1982) 151--164 (in Russian). 


\bibitem{Ale92} 
{\sc V.E. Alekseev}, Range of values of entropy of hereditary classes of graphs, {\it Diskret. Mat}. 4 (1992), no. 2, 148--157 
(in Russian; translation in {\it Discrete Mathematics and Applications}, 3 (1993), no. 2, 191--199).


\bibitem{ABT-theorem}
{\sc N. Alon, J. Balogh, B. Bollob\'{a}s} and {\sc R. Morris},
The structure of almost all graphs in a hereditary property,
{\it J. Combin. Theory} B 79 (2011) 131--156.

\bibitem{SpHerProp} 
{\sc J. Balogh, B. Bollob\'{a}s} and {\sc D. Weinreich}, 
The speed of hereditary properties of graphs, 
{\it J. Combin. Theory} B 79 (2000) 131--156.


\bibitem{BT95} 
{\sc B. Bollob\'{a}s} and {\sc A. Thomason}, 
Projections of bodies and hereditary properties of hypergraphs,
{\it Bull. London Math. Soc.}, 27 (1995) 417--424.

\bibitem{BT97} 
{\sc B. Bollob\'{a}s} and {\sc A. Thomason}, 
Hereditary and monotone properties of graphs, 
``The mathematics of Paul Erd\H os, II'' (R.L. Graham and J. Nesetril, Editors), {\it Alg. and Combin}., 
Vol. 14, Springer-Verlag, New York/Berlin (1997), 70--78.

\bibitem{classes}
A. Brandst\"adt, V.B. Le, J. Spinrad, 
Graph classes: a survey.  SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia, PA, 1999. xii+304 pp. ISBN: 0-89871-432-X.

\bibitem{HalKitPya1} 
{\sc M. Halld\'orsson, S. Kitaev and A. Pyatkin}, Graphs
  capturing alternations in words, {\em Lect. Notes Comput.
    Sci.} 6224 (2010) 436--437. {\em Proc.\ 14th Conf. on
    Developments in Language Theory}, {\em DLT} 2010, London, Ontario,
  Canada, August 17--20, 2010.
  
\bibitem{HalKitPya2} 
{\sc  M. Halld\'orsson, S. Kitaev and A. Pyatkin},
  Alternation graphs, {\em Lect. Notes Comput. Sci.} 6986 (2011) 191--202. Proceedings of the {\em 37th International
    Workshop on Graph-Theoretic Concepts in Computer Science}, {\em
    WG} 2011, Tepl\'a Monastery, Czech Republic, June 21--24, 2011.

\bibitem{KitSei} 
{\sc S. Kitaev and S. Seif}, Word problem of the Perkins
  semigroup via directed acyclic graphs, {\em Order} 25 (2008)
  3, 177--194.

\bibitem{KitPya} 
{\sc S. Kitaev and A. Pyatkin}, On representable graphs, {\em
    J. Autom., Lang. and Combin.} 13 (2008)
  1, 45--54.

\bibitem{KitSalSevUlf1} 
{\sc S. Kitaev, P. Salimov, C. Severs and H. \'Ulfarsson}, On the representability of line graphs, {\em Lecture
    Notes in Computer Science} 6795 (2011) 478--479. {\em Proc.\
    15th Conf. on Developments in Language Theory}, {\em DLT} 2011,
  University of Milano-Bicocca, Milan, Italy, July 19--22, 2011.

\bibitem{KitSalSevUlf2} 
{\sc S. Kitaev, P. Salimov, C. Severs and
  H. \'Ulfarsson}, Word-representability and line graphs, {\em Open
    J. Discr. Math.} 1 (2011) 2, 96--101.
    
% \bibitem{KR}   {\sc D.J. Kleitman and B.L. Rothschild}, Asymptotic enumeration of partial orders on a finite set, {\em Trans. Amer. Math. Soc.} 205 (1975) 205--220. 

\bibitem{S} 
{\sc S. Seif}, Monoids with sub-log-exponential free spectra, {\em J. Pure Appl. Algebra} 212 (2008) 5, 1162--1174.
 
\end{thebibliography}



\end{document}

1307.1810.extracted_bib
\begin{thebibliography}{25}

\bibitem{Ale82} 
{\sc V.E. Alekseev}, 
Hereditary classes and coding of graphs, 
{\it Probl. Cybernet}. 39 (1982) 151--164 (in Russian). 


\bibitem{Ale92} 
{\sc V.E. Alekseev}, Range of values of entropy of hereditary classes of graphs, {\it Diskret. Mat}. 4 (1992), no. 2, 148--157 
(in Russian; translation in {\it Discrete Mathematics and Applications}, 3 (1993), no. 2, 191--199).


\bibitem{ABT-theorem}
{\sc N. Alon, J. Balogh, B. Bollob\'{a}s} and {\sc R. Morris},
The structure of almost all graphs in a hereditary property,
{\it J. Combin. Theory} B 79 (2011) 131--156.

\bibitem{SpHerProp} 
{\sc J. Balogh, B. Bollob\'{a}s} and {\sc D. Weinreich}, 
The speed of hereditary properties of graphs, 
{\it J. Combin. Theory} B 79 (2000) 131--156.


\bibitem{BT95} 
{\sc B. Bollob\'{a}s} and {\sc A. Thomason}, 
Projections of bodies and hereditary properties of hypergraphs,
{\it Bull. London Math. Soc.}, 27 (1995) 417--424.

\bibitem{BT97} 
{\sc B. Bollob\'{a}s} and {\sc A. Thomason}, 
Hereditary and monotone properties of graphs, 
``The mathematics of Paul Erd\H os, II'' (R.L. Graham and J. Nesetril, Editors), {\it Alg. and Combin}., 
Vol. 14, Springer-Verlag, New York/Berlin (1997), 70--78.

\bibitem{classes}
A. Brandst\"adt, V.B. Le, J. Spinrad, 
Graph classes: a survey.  SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia, PA, 1999. xii+304 pp. ISBN: 0-89871-432-X.

\bibitem{HalKitPya1} 
{\sc M. Halld\'orsson, S. Kitaev and A. Pyatkin}, Graphs
  capturing alternations in words, {\em Lect. Notes Comput.
    Sci.} 6224 (2010) 436--437. {\em Proc.\ 14th Conf. on
    Developments in Language Theory}, {\em DLT} 2010, London, Ontario,
  Canada, August 17--20, 2010.
  
\bibitem{HalKitPya2} 
{\sc  M. Halld\'orsson, S. Kitaev and A. Pyatkin},
  Alternation graphs, {\em Lect. Notes Comput. Sci.} 6986 (2011) 191--202. Proceedings of the {\em 37th International
    Workshop on Graph-Theoretic Concepts in Computer Science}, {\em
    WG} 2011, Tepl\'a Monastery, Czech Republic, June 21--24, 2011.

\bibitem{KitSei} 
{\sc S. Kitaev and S. Seif}, Word problem of the Perkins
  semigroup via directed acyclic graphs, {\em Order} 25 (2008)
  3, 177--194.

\bibitem{KitPya} 
{\sc S. Kitaev and A. Pyatkin}, On representable graphs, {\em
    J. Autom., Lang. and Combin.} 13 (2008)
  1, 45--54.

\bibitem{KitSalSevUlf1} 
{\sc S. Kitaev, P. Salimov, C. Severs and H. \'Ulfarsson}, On the representability of line graphs, {\em Lecture
    Notes in Computer Science} 6795 (2011) 478--479. {\em Proc.\
    15th Conf. on Developments in Language Theory}, {\em DLT} 2011,
  University of Milano-Bicocca, Milan, Italy, July 19--22, 2011.

\bibitem{KitSalSevUlf2} 
{\sc S. Kitaev, P. Salimov, C. Severs and
  H. \'Ulfarsson}, Word-representability and line graphs, {\em Open
    J. Discr. Math.} 1 (2011) 2, 96--101.
    
% \bibitem{KR}   {\sc D.J. Kleitman and B.L. Rothschild}, Asymptotic enumeration of partial orders on a finite set, {\em Trans. Amer. Math. Soc.} 205 (1975) 205--220. 

\bibitem{S} 
{\sc S. Seif}, Monoids with sub-log-exponential free spectra, {\em J. Pure Appl. Algebra} 212 (2008) 5, 1162--1174.
 
\end{thebibliography}