Stefan Veldsman

School of Engineering and Mathematical Science, La Trobe University, Melbourne, Australia, and

Department of Mathematics, Nelson Mandela University, Port Elizabeth, South Africa.

veldsman@outlook.com

A basic tool in universal algebra is that of a congruence. It has been shown that congruences can be defined for graphs with properties similar to their universal algebraic counterparts. In particular, a subdirect product of graphs and hence also a subdirectly irreducible graph, can be expressed in terms of graph congruences. Here the subdirectly irreducible graphs are determined explicitly. Using congruences, a graph theoretic version of the well-known Birkhoff Theorem from universal algebra is given. This shows that any non-trivial graph is a subdirect product of subdirectly irreducible graphs.

Keywords: congruence on a graph, quotient graph, subdirect product of graphs, subdirectly irreducible graph, Birkhoff's theorem Mathematics Subject Classification : 05C25, 05C76, 08A30 DOI: 10.5614/ejgta.2020.8.1.9

1. Introduction

Recently, a congruence on a graph was defined by Broere, Heidema and Pretorius [2]. The graphs they consider, do not allow loops. Since there is a direct relationship between a congruence on a graph and a homomorphic image of the graph, the absence of loops makes the theory of

Received: 18 April 2019, Revised: 11 June 2019, Accepted: 23 December 2019.

congruences on such graphs rather restrictive. In [3] this restriction was removed and a theory for congruences on graphs which do admit loops was developed. It was shown that the three classical isomorphism theorems from universal algebra each has a graph theoretical version. Moreover, as for algebras, a subdirect product of graphs can be expressed in terms of congruences. As a first application of these new tools available for graph theory, it was also shown in [3] that a Hoehnke radical can be defined for graphs as was done in universal algebras, and that it determines the connectednesses and disconnectednesses of graphs as defined and developed earlier by Fried and Wiegandt [5]. The connectednesses and disconnectednesses theory of graphs is the graph theoretic version of the classical radical theory of algebraic structures. For the latter, one may consult Gardner and Wiegandt [6] for a comprehensive overview of the radical theory of associative rings.

Here we look at another application of graph congruences culminating in a graph theoretic version of the well-known Birkhoff Theorem in universal algebra [1]: every non-trivial graph is a subdirect product of subdirectly irreducible graphs. The notion of a congruence on a graph is still relatively new and we will start by recalling the definition and basic properties of graph congruences from [3] in the next section. Subdirectly irreducible objects in any category can be thought of as the "primes" (they cannot be decomposed as certain products) and it is desirable to express any object in terms of such irreducible objects. In the third section, we explicitly determine the subdirectly irreducible graphs; such a graph must be one of four namely a two-vertex graph (three possibilities) or a three-vertex graph (only one possibility). It is then proven that any graph with at least two vertices is a subdirect product of such subdirectly irreducible graphs. In [3] it was shown that a subdirect product of graphs can be expressed in terms of congruences and congruences are then also the main tool used to establish the results.

The results presented here are for the category of graphs which admit loops (i.e., a vertex of a graph may have a loop). A version of Birkhoff's Theorem for the category of graphs which do not admit loops was claimed by Fawcett [4] and later proved by Sabidussi [8]. Sabidussi also defined and used the notion of a congruence of a graph in his work (as the kernel of a homomorphism), but he did not develop a theory of congruences for graphs. The category of graphs which admit loops has a much richer homomorphism structure and consequently the subdirectly irreducible graphs considered here are different to those considered by Sabidussi in the category of graphs which do not admit loops.

Let us first fix the terminology and notation required. A graph G with vertex set V and edge set E will typically be denoted by G = (V, E); when we are dealing with different graphs, we may use the notation V^G for V and, similarly, E^G for E. When we write a ∈ G, it actually means a is a vertex of G, i.e., a ∈ VG. By a graph, we mean a non-empty vertex set, edges are not directed, no multiple edges are allowed but loops are. For a, b ∈ G, an edge between a and b will be denoted by ab and aa denotes a loop at a. For a non-empty set D, we use K^D to denote the complete graph with vertex set D and C^D to denote the set of all possible edges and loops on the set D, i.e., C^D = {ab | a, b ∈ D}. If D has cardinality n, we sometimes write Kⁿ and Cⁿ respectively. A (graph) homomorphism is an edge preserving mapping from the vertex set of a graph into the vertex set of a graph. A strong homomorphism is a homomorphism that sends "no edges" to "no edges" and if it is also a bijection, it is called an isomorphism. Isomorphic graphs G and H will be denoted by G ∼= H. For a graph G = (VG, EG), a subgraph H = (VH, EH) of G is a graph with V^H ⊆ V^G

and \(E_H \subseteq E_G\). When \(E_H = \{ab \mid a,b \in V_H \text{ and } ab \in E_G\}\), then H is called a \(strong\ subgraph\) (or \(induced\ subgraph\)) of G. For a homomorphism \(f:G \to H\), the \(image\ graph\ f(G)\) will always be the induced subgraph of H on the vertex set \(f(V_G)\). In general, unless mentioned otherwise, if a subset \(V_H\) of \(V_G\) is regarded as a graph, it will be the subgraph induced by G on \(V_H\). There are two (non-isomorphic) one-vertex graphs, called the \(trivial\ graphs\); the one with a loop \(T_0\) and the one without a loop T. If a graph is not trivial (i.e. with at least two vertices), then it is called non-trivial. The six non-isomorphic two-vertex graphs will be denoted by \(B_i\), i=1,2,3,...,6 where \(V_{B_i}=\{0,1\}\) and \(E_{B_1}=\emptyset\) (empty set), \(E_{B_2}=\{01\}\), \(E_{B_3}=\{00\}\), \(E_{B_4}=\{00,11\}\), \(E_{B_5}=\{01,11\}\) and \(E_{B_6}=\{00,01,11\}\). We will also need one three-vertex graph \(A_3\) with \(A_3=\{0,1,2\}\) and \(A_3=\{00,11,22,01,21\}\). For an equivalence relation C0 on a vertex set C1, we use C2 and C3 and C4 in the set C5. If necessary, it may be written with a subscript as C6. We use C6 and C7 in the set C8 in the set C9 we use C9 be a vertex set C9 where C9 in the set C9 in the set C9 in the set C9. We use C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9 in the set C9

2. Congruences on graphs

For completeness, in this section we recall the definition and basic properties of graph congruences from [3]:

Definition 1. Let \(G = (V_G, E_G)\) be a graph. A congruence on G is a pair \(\theta = (\sim, \mathcal{E})\) where: (i) \(\sim\) is an equivalence relation on \(V_G\); (ii) \(\mathcal{E}\) is the congruence edge-set with \(E_G \subseteq \mathcal{E} \subseteq \mathcal{C}_G\); and (iii) (Substitution Property of \(\mathcal{E}\) with respect to \(\sim\)) for \(x, y \in V_G\), \(xy \in \mathcal{E}\) implies \([x][y] \subseteq \mathcal{E}\).

A strong congruence on G is a pair \(\theta = (\sim, \mathcal{E})\) where \(\sim\) is an equivalence relation on \(V_G\) and \(\mathcal{E} = \mathcal{E}(\sim) := \{xy \mid x, y \in V_G \text{ with } [x][y] \cap E_G \neq \emptyset\}.\)

A strong congruence is also a congruence. Congruences can be partially ordered by the relation "contained in": For two congruences \(\alpha = (\sim_{\alpha}, \mathcal{E}_{\alpha})\) and \(\beta = (\sim_{\beta}, \mathcal{E}_{\beta})\) on G, \(\alpha\) is contained in \(\beta\), written as \(\alpha \subseteq \beta\), if \(\sim_{\alpha} \subseteq \sim_{\beta}\) and \(\mathcal{E}_{\alpha} \subseteq \mathcal{E}_{\beta}\). Let \(\approx\) denote the identity relation (diagonal) on \(V_G\) (i.e., \(x \approx y\) if and only if x = y). The congruence \(\iota_G := (\approx, E_G)\) on G is called the identity congruence on G. It is a strong congruence and is the smallest congruence on G. The universal congruence on G is the pair \(v_G = (\leadsto, \mathcal{C}_G)\) where \(\leadsto\) is the universal relation (i.e., \(a \iff b\) for all \(a, b \in V_G\)). Any congruence on G is contained in \(v_G\). These two congruences, the identity and the universal congruence, are sometimes referred to as the trivial congruences on a graph. For any congruence \(\theta = (\sim, \mathcal{E})\) on a graph G, it is always the case that \(\mathcal{E}(\sim) \subseteq \mathcal{E}\) which means that \(\mathcal{E}(\sim)\) is the smallest congruence edge-set on \(V_G\) for which \((\sim, \mathcal{E}(\sim))\) is a congruence on G. Also note that for any graph \(G = (V_G, E_G)\), \(\mathcal{E}(\approx) = E_G\). The next example is the prototype of all graph congruences.

The kernel of a homomorphism: Given any graph homomorphism \(f: G \longrightarrow H\), the kernel of f, written as \(\ker f = (\sim_f, \mathcal{E}_f)\), is defined by \(\sim_f = \{(x,y) \mid x,y \in V_G, f(x) = f(y)\}\) and \(\mathcal{E}_f = \{uv \mid u,v \in V_G, f(u)f(v) \in E_H\}\). This is a congruence on G. With f is also associated the strong kernel of f, written as \(sker\ f = (\sim_f, \mathcal{E}_{sf})\) with the same equivalence relation but \(\mathcal{E}_{sf} = \mathcal{E}(\sim_f)\). This is a strong congruence on G and \(sker\ f \subseteq \ker f\); in fact, if \(\theta = (\sim_f, \mathcal{E})\) is any congruence on G for some \(\mathcal{E}\), then \(sker\ f \subseteq \theta\). If f is a strong homomorphism, then \(\ker f = sker\ f\). Injectivity of a homomorphism is equivalent to the equivalence relation \(\sim_f\) coinciding with \(\approx\).

Moreover, the kernel of f is the identity congruence on G if and only if f is an injective strong homomorphism. If f is a surjective strong homomorphism, then it is an isomorphism if and only if the kernel of f is the identity congruence.

Quotients: Given any congruence \(\theta = (\sim, \mathcal{E})\) on a graph \(G = (V_G, E_G)\), a new graph, denoted by \(G/\theta = (V_{G/\theta}, E_{G/\theta})\) and called the quotient of G modulo \(\theta\), is defined by taking \(V_{G/\theta} := \{[x] \mid x \in V_G\}\) and \(E_{G/\theta} := \{[x][y] \mid xy \in \mathcal{E}\}\). In this context, the natural (= canonical) mapping \(p_\theta : G \to G/\theta\) given by \(p_\theta(x) = [x]\) is a surjective homomorphism with \(\ker p_\theta = \theta\). In particular, for \(\theta = \iota_G\) we have \(G/\iota_G\) isomorphic to G. If \(\theta\) is a strong congruence, then \(p_\theta\) is a strong homomorphism with \(\ker p_\theta = \theta\). In general, if we take \(\theta = (\mathfrak{D}, \mathcal{E})\) where \(\mathcal{E}\) is any set with \(E_G \subseteq \mathcal{E} \subseteq \mathcal{C}_G\), then \(\theta\) is a congruence on G and \(G/\theta\) is the graph with vertex set \(V_{G/\theta} = V_G\) and edge set \(E_{G/\theta} = \mathcal{E}\) (here we identify \([x] = \{x\}\) with x). If \(v_G\) is the universal congruence on G, then \(G/v_G\) is isomorphic to the trivial graph \(T_0\) (one vertex with a loop).

The lattice of congruences: For a given graph G, the set of all congruences on G is denoted by \(\mathcal{C}(G)\). This set \(\mathcal{C}(G)\) is a partially ordered set with respect to containment \(\subseteq\) as defined above. We can say more. Any collection of congruences \(\{\theta_i = (\sim_i, \mathcal{E}_i) \mid i \in I\} \subseteq \mathcal{C}(G)\) has a greatest lower bound in \(\mathcal{C}(G)\) given by \(\bigcap_{i \in I} \theta_i = (\sim, \mathcal{E})\) where \(a \sim b \Leftrightarrow a \sim_i b\) for all \(i \in I\) and \(ab \in \mathcal{E} \Leftrightarrow ab \in \mathcal{E}_i\) for all \(i \in I\). Moreover, \(\{\theta_i = (\sim_i, \mathcal{E}_i) \mid i \in I\}\) also has a least upper bound in \(\mathcal{C}(G)\) given by the congruence \((\sim, \mathcal{E})\) where \(a \sim b \Leftrightarrow\) there are \(i_1, i_2, \ldots, i_n \in I\) and \(a_{i_1}, a_{i_2}, \ldots, a_{i_n} \in V, n \geq 2\), such that \(a = a_{i_1} \sim_{i_1} a_{i_2} \sim_{i_2} a_{i_3} \sim_{i_3} \cdots \sim_{i_{n-2}} a_{i_{n-1}} \sim_{i_{n-1}} a_{i_n} = b\) and \(\mathcal{E} := \mathcal{E}(\sim) = \{ab \mid a, b \in V \text{ and there is an } i \in I \text{ and } a'b' \in \mathcal{E}_i \text{ with } a' \sim a \text{ and } b' \sim b\}\). It can easily be verified that \((\sim, \mathcal{E})\) is the least upper bound in \(\mathcal{C}(G)\) for \(\{\theta_i = (\sim_i, \mathcal{E}_i) \mid i \in I\}\). We write this least upper bound as \(\bigcup_{i \in I} \theta_i = (\sim, \mathcal{E})\).

Isomorphism theorems for congruences:

For two graphs G and H, let \(f:G\to H\) be a graph homomorphism with \(\theta=(\sim,\mathcal{E})\) a congruence on G and \(\alpha=(\sim_\alpha,\mathcal{E}_\alpha)\) a congruence on H. By \(f(\theta)\) we mean the pair \((f(\sim),f(\mathcal{E}))\) where \(f(\sim)=\{(f(a),f(b))\mid a,b\in V_G,a\sim b\}\) and \(f(\mathcal{E})=\{f(a)f(b)\mid ab\in \mathcal{E}\}\). This need not be a congruence on H, but nevertheless it will be compared to \(\alpha\) in the usual sense, meaning \(f(\theta)\subseteq \alpha\) if and only if \(f(\sim)\subseteq \sim_\alpha\) and \(f(\mathcal{E})\subseteq \mathcal{E}_\alpha\). We start with two auxiliary results and remind the reader that all the results from this section are from [3] which also contains the proofs.

Proposition 2.1. Let \(f: G \to H\) be a homomorphism. Then \(f(\ker f) \subseteq \iota_H\) and if \(\rho = (\sim_{\rho}, \mathcal{E}_{\rho})\) is a congruence on G with \(f(\rho) \subseteq \iota_H\), then \(\rho \subseteq \ker f\).

Proposition 2.2. Let \(f: G \to H\) and \(g: G \to K\) be surjective homomorphisms. Then \(\ker f = (\sim_f, \mathcal{E}_f) \subseteq \ker g = (\sim_g, \mathcal{E}_g)\) if and only if there is a homomorphism \(h: H \to K\) such that \(h \circ f = g\).

This brings us to:

Theorem 2.1. (First Isomorphism Theorem) Let \(f: G \to H\) be a homomorphism. Then \(G/\ker f\) is isomorphic to f(G) where f(G) is the induced subgraph of H on \(f(V_G)\). If f is surjective, then \(G/\ker f\) is isomorphic to H. Moreover, if f is a surjective strong homomorphism, then \(G/\operatorname{sker} f\) is isomorphic to H.

Let G be a graph with induced subgraph H. Then a congruence θ = (∼, E) on G induces a congruence H ∩ θ = (∼H, EH) on H with ∼H= (V^H × VH)∩ ∼ = {(a, b) | a, b ∈ V^H and a ∼ b} and E^H = {ab | a, b ∈ VH} ∩ E = {ab | a, b ∈ V^H with ab ∈ E}. The mapping f : H → G/θ defined by f(a) = [a] for all a ∈ V^H is a homomorphism with ker f = H ∩ θ. Now f(VH) is a set of vertices of G/θ on which we form the induced subgraph of G/θ, denoted by (H + θ)/θ. Then, by the First Isomorphism Theorem, we have:

Theorem 2.2. (Second Isomorphism Theorem) Let H be an induced subgraph of a graph G. Let θ be a congruence on G. Then H ∩θ is a congruence on H and H/H ∩θ is isomorphic to (H +θ)/θ where the latter graph is the induced subgraph of G/θ on the vertex set {[a] | a ∈ VH}.

Theorem 2.3. (Third Isomorphism Theorem) Let G be a graph and let θ¹ = (∼1, E1) and θ² = (∼2, E2) be two congruences on G with θ¹ ⊆ θ2. Then θ2/θ¹ := (∼, E) is a congruence on G/θ¹ where the equivalence is given by [a]¹ ∼ [b]¹ ⇔ a ∼² b and the congruence edge-set is given by [a]1[b]¹ ∈ E ⇔ ab ∈ E2. Moreover, the quotient graph (G/θ1)/(θ2/θ1) is isomorphic to the quotient graph G/θ2.

This theorem gives the expected connection between the congruences on a graph and the congruences on an associated quotient graph.

Theorem 2.4. Let G be a graph with θ a fixed congruence on G. Any congruence ξ of the graph G/θ is of the form α/θ for some congruence α on G with θ ⊆ α. Moreover, there is a one-to-one correspondence between {α | α is a congruence on G with θ ⊆ α} and C(G/θ) which preserves inclusions, intersections and unions of congruences.

Products and subdirect products of graphs:

For an index set I, let Gⁱ = (Vⁱ , Ei) be a graph for all i ∈ I. The product Q i∈I Gⁱ of the graphs Gⁱ is the graph Q i∈I Gi := (Q i∈I Vi , E) where Q i∈I Vi is just the usual Cartesian product of the sets Vⁱ and E = {fg | f, g ∈ Q i∈I Vⁱ with f(i)g(i) ∈ Eⁱ for all i ∈ I}. For every j ∈ I, the j-th projection πj : Q i∈I Gⁱ → G^j defined by π^j (f) = f(j) for all f ∈ Q i∈I Vi is a surjective homomorphism. An induced subgraph H of Q i∈I Gi is called a subdirect product of the graphs Gⁱ , i ∈ I, provided the restriction of each projection π^j to H is a surjective mapping onto G^j . As in universal algebra, subdirect products can be expressed in terms of congruences and quotients:

Theorem 2.5. For each i ∈ I, let θⁱ be a congruence on a graph G with θ := T i∈I θi . Then G/θ is isomorphic to a subdirect product of the quotient graphs G/θⁱ , i ∈ I.

In particular, it then follows that:

Corollary 2.1. A graph G is a subdirect product of graphs Gⁱ , i ∈ I, if and only if for every i ∈ I there are congruences θⁱ on G with Gⁱ isomorphic to G/θⁱ and T i∈I θⁱ = ιG.

3. Subdirectly irreducible graphs.

A graph G is called subdirectly irreducible if the following condition is fulfilled: whenever Gis a subdirect product of graphs \(G_i\), \(i \in I\) for some index set I, then \(G \cong G_i\) for at least one \(j \in I\). In terms of congruences, this means that G is subdirectly irreducible if and only if whenever \(\theta_i\) is a congruence on G for all i from some some index set I with \(\cap \theta_i = \iota_G\), then \(\theta_i = \iota_G\) for some \(j \in I\). If G is not subdirectly irreducible, it is called subdirectly reducible. In layman's terms, this means that a subdirectly reducible graph sits tightly in a product of graphs, none of which coincides with G.

The two-vertex graph \(B_6\) has only the two trivial congruences \(\iota_{B_6}\) and \(\upsilon_{B_6}\) and is subdirectly irreducible; \(B_5\) and \(B_4\) each has three congruences, the two trivial congruences as well as \((\approx,\)\(\{00, 01, 11\}\)) and both are subdirectly irreducible. The graphs \(B_3\) and \(B_2\) each has five congruences and \(B_1\) has nine. These three graphs are subdirectly reducible: \(B_1\) is a subdirect product of \(B_4\) and two copies of \(B_5\) using the congruences \(\gamma_1 = (\Leftrightarrow, E_1 = \{00, 11\}), \gamma_2 = (\Leftrightarrow, E_2 = \{00, 01\})\) and \(\gamma_3 = (\Leftrightarrow, E_3 = \{01, 11\}); B_2\) is a subdirect product of two copies of \(B_5\) (using the congruences \(\gamma_2\)and \(\gamma_3\)) and \(B_3\) is a subdirect product of \(B_4\) and \(B_5\) (using \(\gamma_1\) and \(\gamma_3\)). For ease of reference, we record this here as our first result.

Proposition 3.1. The two-vertex graphs \(B_4\), \(B_5\) and \(B_6\) are subdirectly irreducible. The two-vertex graphs \(B_1\), \(B_2\) and \(B_3\) are subdirectly reducible being subdirect products of copies of \(B_4\) and \(B_5\).

We also need:

Proposition 3.2. Suppose the graph G is a subdirect product of the graphs \(G_i\), \(i \in I\), and for some \(i_0 \in I, G_{i_0}\) is a subdirect product of graphs \(H_j\) for \(j \in J\) (take \(I \cap J = \emptyset\)). Then G is a subdirect product of the graphs \(K_r\) for \(r \in R := J \cup (I - \{i_0\})\) where \(K_r = \begin{cases} G_r \text{ if } r \in I - \{i_0\} \\ H_r \text{ if } r \in J \end{cases}.\)

\[K_r = \begin{cases} G_r & \text{if } r \in I - \{i_0\} \\ H_r & \text{if } r \in J \end{cases}\]

Proof. By Corollary 2.9 there are congruences \(\theta_i\) on G with \(G_i\) isomorphic to \(G/\theta_i\) and \(\bigcap_{i \in I} \theta_i = \iota_G\)and congruences \(\eta_j\) on \(G_{i_0}\) with \(H_j\) isomorphic to \(G_{i_0}/\eta_j\) and \(\bigcap_{i\in I}\eta_j=\iota_{G_{i_0}}\). By Theorem 2.7, there are congruence \(\alpha_j\) on G with \(\theta_{i_0} \subseteq \alpha_j\) such that \(\bigcap_{j \in J} \alpha_j = \theta_{i_0}\) and \(\eta_j = \alpha_j/\theta_{i_0}\). Then

\[\begin{pmatrix} \bigcap_{i \in I - \{i_0\}} \theta_i \end{pmatrix} \cap \begin{pmatrix} \bigcap_{j \in J} \alpha_j \end{pmatrix} = \begin{pmatrix} \bigcap_{i \in I - \{i_0\}} \theta_i \end{pmatrix} \cap \theta_{i_0} = \bigcap_{i \in I} \theta_i = \iota_G. \text{ The result follows from Theorem } 2.6 \text{ since } G/\alpha_j \cong (G/\theta_{i_0})/(\alpha_j/\theta_{i_0}) \cong G_{i_0}/\eta_j \cong H_j \text{ for all } j \in J.\]

We now determine the subdirectly irreducible graphs in a series of intermediate results. For this we often use the following congruences: For a graph \(G=(V_G,E_G)\), let \(a\in G\) and let \(\rho_a := (\sim_a, \mathcal{E}_a)\) be the congruence on G where \(\sim_a\) is the equivalence on \(V_G\) with two equivalence classes \([a]=\{a\}\) and \([b]=V_G-\{a\}\) for \(b\neq a\), and \(\mathcal{E}_a=\mathcal{E}(\sim_a)\). If G has more than three vertices, then \(\rho_a \neq \iota_G\). Clearly \(aa \in \bigcap_{b \in G} \mathcal{E}_b \Leftrightarrow aa \in E_G \Leftrightarrow aa \in \mathcal{E}_a\). Note also that \(\bigcap_{a \in G} \rho_a = (\mathfrak{D}, \mathcal{E})\) where

\[E_G \subseteq \mathcal{E} = \bigcap_{a \in G} \mathcal{E}_a.\]

Proposition 3.3. Let G be a non-trivial graph with E^G = ∅. Then G is a subdirect product of |G| copies of the two-vertex graph B¹ and hence also a subdirect product of the subdirectly irreducible graphs B⁴ and B5.

Proof. For every a ∈ G, the congruence ρ^a defined above is given here by ρ^a = (∼a, EG) and G/ρ^a ≡ B1. Moreover, T a∈G ρ^a = ι^G and so we have G is a subdirect product of copies of B1. The last part follows from the previous two propositions.

Proposition 3.4. Let G be a non-trivial graph with E^G = CG; i.e., G is complete with all loops. Then G is a subdirect product of |G|-copies of the subdirectly irreducible two-vertex graph B6; hence G is subdirectly reducible.

Proof. Here we have for every a ∈ G, the congruence ρ^a = (∼a, EG) and G/ρ^a ∼= B6. Moreover, T a∈G ρ^a = ι^G and hence G is a subdirect product of copies of B6.

Because any induced subgraph of a product of copies of the graph B⁶ will be complete with all loops, we have:

Corollary 3.1. A non-trivial graph G is complete with all loops if and only if G is a subdirect product of copies of the graph B6.

Theorem 3.1. Let G be a non-trivial graph. Then G is subdirectly irreducible if and only if G is one of the four graphs B4, B5, B⁶ or A3.

Proof. Already we know that the two-vertex graphs B4, B⁵ and B⁶ are subdirectly irreducible. A direct verification shows that A³ = ({0, 1, 2}, {00, 11, 22, 01, 12}) has 6 congruences and any intersection of congruences which is the identity must already contain one that is the identity; hence A³ is subdirectly irreducible. The converse will be shown in a number of steps:

(1) Let G be a graph with at least three vertices. If G is subdirectly irreducible, then every vertex of G has a loop.

Proof of (1): Suppose G has a vertex p which does not have a loop. Let γ be the congruence γ = (m, Eγ) where E^γ = E^G ∪ {pp}). Then γ 6= ι^G and also ρ^a 6= ι^G for all a ∈ G. Now γ ∩ T a∈G ρa = (m, EG) = ιG. Indeed, for the first equality, we note that E^γ ∩ T a∈G Ea = E^G :

if st ∈ E^γ ∩ T a∈G Ea , then st ∈ E^G or st = pp. But st is also in E^a for all a ∈ G. In particular, if st = pp we get for a = p, that pp = st ∈ E^p and so pp ∈ EG; a contradiction. Thus st ∈ E^G and hence γ ∩ T a∈G ρa = ιG. But this contradicts the fact that G is subdirectly irreducible.

(2) Let G be a non-trivial complete graph with all loops. Then G is subdirectly irreducible if and only if G is a two-vertex graph.

Proof of (2): By assumption, G has at least two-vertices and E^G = CG. If G has only two vertices, then G = B⁶ which we already know is subdirectly irreducible. Conversely, suppose G is subdirectly irreducible. For every a ∈ G, the congruence ρ^a = (∼a, Ea) = (∼a, CG) and

T a∈G ρa = ιG. By the assumption on G, there is an a ∈ G with ρ^a = ιG. This implies that |VG| = 2 and we are done.

(3) Let G be a graph with at least three vertices. If G is subdirectly irreducible, then G has all loops and all but one edge; i.e., E^G = C^G − {ab} for two distinct vertices a, b ∈ G.

Proof of (3): By (1) we already know that aa ∈ E^G for all a ∈ G. By (2) G is not complete, say a, b ∈ G with ab ∈ C^G − E^G and a 6= b. For any pq ∈ C^G − EG, we have p 6= q. Let θpq be the congruence θpq = (m, Epq) with Epq = E^G ∪ {pq}. Clearly θpq 6= ιG. If pq 6= ab, then θpq ∩θab = ι^G which contradicts G subdirectly irreducible. Thus E^G = C^G − {ab} as required.

This gives:

• (4) Let G be a graph with three vertices. Then G is subdirectly irreducible if and only if G = A3.
• (5) Let G be a graph with at least four vertices. Then G is subdirectly reducible.

Proof of (5): If not, then by (3) we have E^G = C^G − {pq} for two distinct p, q ∈ G. Let α = (∼α, Eα) be the congruence with ∼αthe equivalence on G with equivalence classes {p, q} and {a} for all a ∈ G− {p, q} and E^α = CG. Clearly α 6= ιG. Let ∼^β be the equivalence on G with the three equivalence classes {p}, {q} and V^G − {p, q} and let E^β = EG. Then β = (∼β, Eβ) is a congruence on G. Indeed, for this we verify the Substitution Property: pp ∈ E^G ⇒ [p]β[p]^β = {pp} ⊆ EG; qq ∈ E^G ⇒ [q]β[q]^β = {qq} ⊆ EG; for a ∈ V^G − {p, q}, pa ∈ E^G ⇒ [p]β[a]^β = {pt | t 6= p, t 6= q} ⊆ E^G and likewise qa ∈ E^G ⇒ [q]β[a]^β ⊆ E^G and lastly, for a, b ∈ V^G − {p, q}, ab ∈ E^G ⇒ [a]β[b]^β = {st | s, t ∈ V^G − {p, q}} ⊆ EG. Thus β is a congruence and since G has at least four vertices, β 6= ιG. But α ∩ β = ιG; hence G is subdirectly reducible.

We now show the converse of the statement in the theorem. Let G be a non-trivial graph which is subdirectly irreducible. By (5), G must have two or three vertices. If |G| = 2, G can only be one of B4, B⁵ or B⁶ and if G has three vertices, then by (4) above it must be the graph A3.

4. Birkhoff's Theorem for graphs

We conclude with the graph theoretic version of Birkhoff's Theorem.

Theorem 4.1. Every non-trivial graph is a subdirect product of subdirectly irreducible graphs; i.e., every non-trivial graph is an induced subgraph of a product of copies of the graphs B4, B5, B⁶ and A3.

Proof. If G has only two vertices, then the statement follows from Proposition 3.1. Suppose thus G has at least three vertices. Then the congruence ρ^a = (∼a, Ea) is not the identity and G/ρ^a is one of the two-vertex graphs ^Bi for every ^{a ∈} G. Thus, if T a∈G ρa = ιG, i.e. if E^G = T a∈G Ea, we are done by Propositions 3.1 and 3.2. Suppose thus E^G ⊂ T a∈G Ea, say p, q ∈ G with pq ∈ E^a for all a ∈ G but pq /∈ EG. In particular, pq ∈ Ep. This means p 6= q, for if p = q, then pp ∈ E^p implies pq = pp ∈ EG; a contradiction. Since pq ∈ Ep, we know [p]p[q]^p ⊆ E^p and so there is an r ∈ V^G − {p} with pr ∈ EG. Note that r 6= q. Likewise, since pq ∈ E^q there is an s ∈ V^G − {p, q} with qs ∈ E^G (we could have r = s). Let ∼pq be the equivalence on V^G with three equivalence classes {p}, {q} and V^G − {p, q}. Let Epq := C^G − {pq}. Clearly E^G ⊆ Epq and to justify the claim

that \(\gamma_{pq} := (\sim_{pq}, \mathcal{E}_{pq})\) is a congruence on G, we will verify the Substitution Property. Let \(ab \in \mathcal{E}_{pq}\). Then \(ab \neq pq\) and

\[[a]_{pq}[b]_{pq} = \begin{cases} \{pp\} \text{ if } a = b = p \\ \{qq\} \text{ if } a = b = q \\ \{pt \mid t \in V_G - \{p,q\}\} \text{ if } a = p \text{ and } b \in V_G - \{p,q\} \\ \{qt \mid t \in V_G - \{p,q\}\} \text{ if } a = q \text{ and } b \in V_G - \{p,q\} \\ \{tu \mid t, u \in V_G - \{p,q\}\} \text{ if } a, b \in V_G - \{p,q\} \end{cases}\] we have \([a]_{pq}[b]_{pq} \subseteq \mathcal{E}_{pq}\). Hence \(\gamma_{pq}\) is a congruence on \(G\).

from which we have \([a]_{pq}[b]_{pq} \subseteq \mathcal{E}_{pq}\). Hence \(\gamma_{pq}\) is a congruence on G.

We now distinguish two cases. If \(\gamma_{pq} = \iota_G\), then \(V_G = \{p, q, r\}\) and \(E_G = \mathcal{E}_{pq} = \mathcal{C}_G - \{pq\}\). This means \(G = A_3\) and we are done. Suppose thus \(\gamma_{pq} \neq \iota_G\) for all \(pq \in \bigcap_{a \in G} \mathcal{E}_a - E_G\). Note that for

all these \[pq\]'s we have \(G/\gamma_{pq}\cong A_3\). We also have \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\) = \(E_G\) for if \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\) and \(st\notin E_G\), then \(st\in\bigcap_{a\in G}\mathcal{E}_a-E_G\) and \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\). This means \(st\in\mathcal{E}_{st}=\mathcal{C}_G-\{st\}\); a contradiction. Hence \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\) = \(E_G\) and so \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\) = \(E_G\) and so \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\) = \(E_G\)

5. Conclusion

Graph congruences is a relatively new concept. A few applications to demonstrate how this new tool can be used in graph theory have been given. The flavor and results for graphs follow closely the motivating influences from universal algebra. Already it has been shown that the classical radical theory of algebras which has also been developed for graphs under the guise of connectednesses and diconnectednesses, can be obtained from congruences as for their algebraic counterparts. Here another classical algebraic application of congruences for graphs, namely Birkhoff's Theorem, is given: Every graph with at least two vertices is a subdirect product of subdirectly irreducible graphs. In addition, all the subdirectly irreducuble graphs are determined explicitly. It is shown that there are exactly four such graphs; three with two vertices each and one with three vertices.

References

• [1] G. Birkhoff, Subdirect unions in universal algebra, Bull. Amer. Math. Soc. 50 (1944) 764 768.
• [2] I. Broere, J. Heidema and L.M. Pretorius, Graph congruences and what they connote, Quaest. Math. 41 (2018), 1045–1058.
• [3] I. Broere, J. Heidema and S. Veldsman, Congruences and Hoehnke Radicals on Graphs, Discuss. Math. Graph Theory. To appear.

• [4] B. Fawcett, Graphs and ultrapowers. PhD Thesis, McMaster University (1969).
• [5] E. Fried and R. Wiegandt, Connectednesses and disconnectednesses of graphs, Algebra Universalis 5 (1975), 411–428.
• [6] B.J. Gardner and R. Wiegandt, The Radical Theory of Rings, Marcel Dekker Inc., New York (2004).
• [7] H.-J Hoehnke, Radikale in algemeinen Algebren, Mathematische Nachrichten 32 (1966), 347– 383.
• [8] G. Sabidussi, Subdirect representations of graphs. Coll. Math. Soc. Janos Bolyai 10 Infinite and finite sets (Kesztheley, Hungary, 1973), North Holland, Amsterdam 1199 - 1226 (1975).