Un grafo es un par \((G,r)\) donde \(G\) es un conjunto no vacío y \(r\) es una relación binaria sobre \(G\) tal que:
adhocprefix-adhocsufix \((x,x)\notin r\), cualesquiera sea \(x\in G\)
adhocprefix-adhocsufix Si \((x,y)\in r\), entonces \((y,x)\in r\), cualesquiera sean \(x,y\in G\) (es decir, \(r\) es simétrica con respecto a \(G\))
Hay varias presentaciones del concepto de grafo no dirigido pero el lector no tardara en darse cuenta que estas estructuras son equivalentes a las que el haya estudiado bajo el nombre de grafos no dirigidos. Los elementos de \(G\) son llamados los vértices de \((G,r)\). Cuando \((x,y)\in r\) diremos que \(x\) e \(y\) son adyacentes o están conectados.
Dado que no hay operaciones distinguidas ni elementos distinguidos en este tipo de estructuras, los términos elementales de grafos serán las variables y los nombres de elementos fijos. Dado un grafo \((G,r)\), escribiremos \(r(x,y)\) para expresar que \((x,y)\in r\). Con esta convención las fórmulas elementales de grafos se definen con las siguientes clausulas:
adhocprefix(1)adhocsufix Si \(t\) y \(s\) son términos elementales de grafos, entonces la palabra \((t=s)\) es una fórmula elemental de grafos
adhocprefix(2)adhocsufix Si \(t\) y \(s\) son términos elementales de grafos, entonces la palabra \(r(t,s)\) es una fórmula elemental de grafos
adhocprefix(3)adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son fórmulas elementales de grafos, entonces la palabra \((\varphi_{1}\wedge\varphi_{2})\) es una fórmula elemental de grafos
adhocprefix(4)adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son fórmulas elementales de grafos, entonces la palabra \((\varphi_{1}\vee\varphi_{2})\) es una fórmula elemental de grafos
adhocprefix(5)adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son fórmulas elementales de grafos, entonces la palabra \((\varphi_{1}\leftrightarrow\varphi_{2})\) es una fórmula elemental de grafos
adhocprefix(6)adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son fórmulas elementales de grafos, entonces la palabra \((\varphi_{1}\rightarrow\varphi_{2})\) es una fórmula elemental de grafos
adhocprefix(7)adhocsufix Si \(\varphi\) es una fórmula elemental de grafos, entonces la palabra \(\lnot\varphi\) es una fórmula elemental de grafos
adhocprefix(8)adhocsufix Si \(\varphi\) es una fórmula elemental de grafos, entonces las palabras \[\forall x\varphi\;\;\;\forall y\varphi\;\;\;\forall z\varphi\;\;\;...\] son fórmulas elementales de grafos
adhocprefix(9)adhocsufix Si \(\varphi\) es una fórmula elemental de grafos, entonces las palabras \[\exists x\varphi\;\;\;\exists y\varphi\;\;\;\exists z\varphi\;\;\;...\] son fórmulas elementales de grafos
adhocprefix(10)adhocsufix Una palabra es una fórmula elemental de grafos si y solo si se puede construir usando las clausulas anteriores
Debería quedar claro que arriba \(r(t,s)\) denota el resultado de concatenar las 6 siguientes palabras \[r\;\;\;\;\;\;(\;\;\;\;\;\;t\;\;\;\;\;\;,\;\;\;\;\;\;s\;\;\;\;\;\;)\] es decir que \(r(t,s)\) es una palabra de longitud \(\left|t\right|+\left|s\right|+4\).
Cabe destacar que esta definición de fórmula elemental de grafos no es una definición matemática precisa.
Por supuesto, los términos o fórmulas elementales de grafos en los cuales no ocurran nombres de elementos fijos serán llamados puros. O sea que en este caso solo las variables serán términos elementales puros de grafos.
Veamos algunas definiciones básicas de grafos. Dado un grafo \((G,r)\) y \(x\in G\) la valencia de \(x\) es el cardinal del conjunto \(\{y:(x,y)\in r\}\). Diremos que un subconjunto \(S\subseteq G\) es una clique cuando se dé que \((x,y)\in r\) cada ves que \(x,y\) sean elementos distintos de \(S\). Dado \(n\geq2\), un \(n\)-ciclo de \((G,r)\) será una sucesión \(x_{1},x_{2},...,x_{n}\) la cual cumpla que
adhocprefix-adhocsufix \(x_{i}\text{ es distinto de }x_{j}\), siempre que \(i\text{ sea distinto de }j\)
adhocprefix-adhocsufix \((x_{i},x_{i+1})\in r\), para \(i=1,...,n-1\)
adhocprefix-adhocsufix \((x_{n},x_{1})\in r\)
Dejamos al lector que se ejercite intentando dar:
adhocprefix-adhocsufix Una fórmula elemental pura de grafos que tenga a \(x\) como su única variable libre la cual "diga" \(x\) tiene valencia 3
adhocprefix-adhocsufix Una sentencia elemental pura de grafos que sea verdadera en un grafo \((G,r)\) si y solo si \((G,r)\) no tiene cliques de cardinal 4
adhocprefix-adhocsufix Una sentencia elemental pura de grafos que sea verdadera en un grafo \((G,r)\) si y solo si \((G,r)\) no tiene 4-ciclos