Un grafo es un par \((G,r)\) donde \(G\) es un conjunto no vacio y \(r\) es una relacion 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 simetrica 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 vertices de \((G,r)\). Cuando \((x,y)\in r\) diremos que \(x\) e \(y\) son adyacentes o estan conectados.
Dado que no hay operaciones distinguidas ni elementos distinguidos en este tipo de estructuras, los terminos elementales de grafos seran las variables y los nombres de elementos fijos. Para las formulas elementales de grafos escribiremos \(r(x,y)\) para expresar que \((x,y)\in r\). Con esta convencion las formulas elementales de grafos se definen con las siguientes clausulas:
adhocprefix-adhocsufix Si \(t\) y \(s\) son terminos elementales de grafos, entonces la palabra \((t=s)\) es una formula elemental de grafos
adhocprefix-adhocsufix Si \(t\) y \(s\) son terminos elementales de grafos, entonces la palabra \(r(t,s)\) es una formula elemental de grafos
adhocprefix-adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son formulas elementales de grafos, entonces \((\varphi_{1}\wedge\varphi_{2})\) es una formula elemental de grafos
adhocprefix-adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son formulas elementales de grafos, entonces \((\varphi_{1}\vee\varphi_{2})\) es una formula elemental de grafos
adhocprefix-adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son formulas elementales de grafos, entonces \((\varphi_{1}\leftrightarrow\varphi_{2})\) es una formula elemental de grafos
adhocprefix-adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son formulas elementales de grafos, entonces \((\varphi_{1}\rightarrow\varphi_{2})\) es una formula elemental de grafos
adhocprefix-adhocsufix Si \(\varphi\) es una formula elemental de grafos, entonces \(\lnot\varphi\) es una formula elemental de grafos
adhocprefix-adhocsufix Si \(\varphi\) es una formula elemental de grafos, entonces las palabras \[\forall x\varphi\;\;\;\forall y\varphi\;\;\;\forall z\varphi\;\;\;...\] son formulas elementales de grafos
adhocprefix-adhocsufix Si \(\varphi\) es una formula elemental de grafos, entonces las palabras \[\exists x\varphi\;\;\;\exists y\varphi\;\;\;\exists z\varphi\;\;\;...\] son formulas elementales de grafos
adhocprefix-adhocsufix Una palabra es una formula elemental de grafos si y solo si se puede construir usando las clausulas anteriores
Deberia 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\).
Por supuesto, los terminos o formulas elementales de grafos en los cuales no ocurran nombres de elementos fijos seran llamados puros. O sea que en este caso solo las variables seran terminos elementales puros de grafos.
Veamos algunas definiciones basicas 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 de que \((x,y)\in r\) cada ves que \(x,y\) sean elementos distintos de \(S\). Dado \(n\geq2\), un \(n\)-ciclo de \((G,r)\) sera una sucecion \(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 formula elemental pura de grafos que tenga a \(x\) como su unica 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