SOME THEOREMS ON ABSTRACT GRAPHS

By G. A. DIRAC
[Received 4 April 1951.—Read 19 April 1951]
A GRAPH is a set Jf whose members are called the nodes together with a
set (f of unordered pairs of unequal members of Jf called the edges. In this
paper nodes will generally be denoted by small letters a, b, etc., possibly with
suffixes, and edges by (a, b), etc., where a =£ b and {a, b) = (b, a). Each of the
nodes a and b is called an end node of the edge (a, b) and these two nodes are
said to he joined by the edge or to be adjoint to the edge. A graph is finite if
the set of its nodes is finite, otherwise it is infinite. The order of a graph is
the (cardinal) number of the set of its nodes. A subgraph is a graph whose sets
of nodes and edges are subsets of the sets of nodes and edges of the graph.
The number of edges adjoint to a node is called the degree of the node.
A path is a graph whose nodes are av a2, a3,..., an) where n ^ 2 and
different suffixes denote different nodes, and whose edges are (av a2),
(a2>%)>•••> (an-van)- A circuit is a graph whose nodes are av a2, a3,..., am,
where m ^ 3 and different suffixes denote different nodes, and whose
edges are (av a2), (a2, a3),..., (am_1, am), (am, a^). The length of a path (circuit)'
is the number of edges in the path (circuit).
A graph is connected if any two nodes in it are connected by a path,
otherwise it is disconnected. A node is a cut-node if it divides the graph
into two or more disconnected components.
A graph has chromatic number k (is k-chromatic) if k is the least positive
integer having the property that the nodes of the graph can be divided
into k mutually disjoint classes so that no two nodes in the same class are
joined by an edge.
A complete h-graph is a graph having h nodes, every pair of distinct
nodes being joined by an edge.
In the first part of this paper we shall obtain some relations between the
degrees of the nodes in a graph and the lengths of the circuits contained
in it, in the second part we will use them to obtain some relations between
the chromatic number of a graph and the lengths of the circuits contained
in it.
I
THEOREM 1. A graph without a cut-node which contains arbitrarily long
paths contains arbitrarily long circuits.
To prove this theorem we prove that
A graph without a cut-node which contains a path of length I > 1 contains
a circuit of length exceeding
Proc. London Math. Soc. (3) 2 (1952)
70 G. A. DIRAC
Let a0, ax, a2,..., at be the nodes of the path of length I in order from
one end to the other, and let this path be denoted by W. Let A be the
number of edges in one of the longest circuits of the graph. (If the graph
contains arbitrarily long circuits there is nothing to prove.)
The graph has no cut-node, hence by Menger's theoremf there are two
paths in it connecting aQ and at which have no nodes except a0 and at in
common. We denote two such paths by Wx and W2.
Let Wx have wx O 0) nodes in common with W not counting a0 and ah
and let W2 have w2 ( ^ 0) nodes in common with W not counting a0 and at.
The two paths Wx and W2 together constitute a circuit with at least
Wi-f-M>2+2 ( ^ 3) edges. Hence
wx+w'2+2 ^ A. (i)
The intersections of Wx and W divide W into wx+l portions, and each
of these portions together with the portion of Wx connecting its end nodes
forms a circuit, and at least one of these circuits contains more than
l/(wx-\-l) edges. Hence
l/{wx-\-l) < A, and similarly l/{w2-\-l) < A. (ii)
From (ii) w x + l > IIA and w2-\-l > I/A.
So from (i) 21/A <A and so A > V(2Z).
This proves Theorem 1. Actually A > 2VZ, but the proof of this result,
which is best possible, is rather complicated.

THEOKEM 2. A finite graph in which the degree of every node is at least d

( > 1) contains a circuit of length at least d-\-\.
Proof. Let W be one of the longest paths in the graph, and let the
nodes of W in order from one end to the other be ax, a2, a3,..., at. Then
ax is joined only to nodes from among a2, a3, a4,..., at otherwise W would
not be one of the longest paths in the graph, and it is joined to at least d
of these. Let ai be the node with largest suffix to which ax is joined, then
i ^ d-\-\. The nodes av a2, a3,..., ai,a1 in this order lie on the circuit
formed by the portion of W connecting ax and at and the edge (a^a^.
The circuit has length i and » ^ d+1; hence the theorem is proved.
Theorem 2 is best possible; this is shown by the complete (d+1)-graph.
It is also best possible for connected graphs of arbitrarily high order; this
is shown by the graph consisting of a number of complete (d-j-l)-graphs
Vx, r2>... which are mutually disjoint except for one (and only one) node
f G. Haj6s, 'Zum Mengerschen Graphensatz', Acta Litterarum ac Scientiarum
(Sectio Scientiarum Mathematicarum), Szeged, 7, 1934, 44-47. D. Konig, Theorie
der endlichen und unendlichen Oraphen (Leipzig, 1936), Kap. xiv.
 SOME THEOREMS ON ABSTRACT GRAPHS 71
which they all have in common; and by the graph consisting of a number
of complete (d-f-1)-graphs Fi, F'2, r"3,..., where F^ and FJ- are disjoint if
i =£ j and \i—j\ ^ 2 and F^ and Fj have one and only one node in common
if i =fi j and \i—j\ = 1. The graphs in these examples, except for the
complete (d-f-l)-graph> have one or more cut-nodes. For graphs without
a cut-node Theorem 2 is not best possible; this will be proved in Theorem 4.
The method of proof of Theorem 2 also provides a result which will be
needed in the proof of Theorem 4:
LEMMA 1. An infinite graph without a cut-node in which the degree of
every node is at least d ( > 1) contains a circuit of length at least d-\-\.
Proof. By Theorem 1 the lemma is true if the graph contains arbitrarily
long paths. It remains to prove it if the lengths of the paths contained in
the graph are bounded. In this case let W be one of the longest paths
contained in the graph, and let the nodes of W from one end to the other
be av a2,..., at. From here the proof is the same as the proof of Theorem 2.
The requirement that the graph should have no cut-node is essential;
otherwise, for example, the graph may be a tree in which the degree of
every node is at least d ( > 1). Lemma 1 is not best possible; this will be
proved in Theorem 4.
The following result concerns finite graphs:
DEFINITION. A graph is said to be Hamiltonian if it contains a circuit
which embraces all the nodes of the graph. It follows from the definition
that a Hamiltonian graph is finite and connected and has no cut-node.
THEOREM 3. A connected graph in which the degree of every node is at least
d ( > 1) and which has not more than 2d nodes is Hamiltonian.
Proof. Suppose the theorem false, so that for some value of d > 1 there
is a graph F of order n ^ 2d which is not Hamiltonian.
Let ^ be one of the longest circuits contained in F and let the nodes
of *$ in cyclic order be ax, a2, a3,..., ac. By Theorem 2 c ^ d-\-l, by
hypothesis c < ?i— 1 < 2d—l. At least one of the nodes of # is connected
to a node of F which is not in #, and without loss of generality this node
can be taken to be ac.
Let V be one of the longest among those paths of F which start from ac and
which have no node except ac in common with ^'. Let ac, ac+1, ac+2,..., ac+e
(e ^ 1) be the nodes of V in order starting from ac.
We now prove that e ^ d.
Suppose, on the contrary, that e ^ d— 1. Because V is one of the
longest among those paths of F which start from ac and which have no
node except ac in common with %>, ac+e is joined only to nodes among
72 G. A. DIRAC
ax, a2,..., ac, ac+v..., ac+e_x and it is therefore joined to at least d of these.
Hence ac+e is joined to at least d—e ( ^ 1) nodes of ^ besides ac.
If ac+e is joined to a node ai of ^ different from ac then i > e + 1 . For
the path whose nodes in order are ac+e, at, ai+1, ai+2,..., ac and V together
form a circuit of length c-fe+1—i, and 9? is one of the longest circuits in
the graph, so c-f-e+1 —i < c and hence * > e + 1 . Similarly i < c—c— 1.
Sofflc+eis joined to at least d—e ( > 1) of the nodes ae+v ae+2,..., ac_c_2, ac_c_.x.
These nodes number c—2e— 1.
Now ac+e is not joined to two neighbouring nodes of 9?, because if it were
9? would clearly not be one of the longest circuits of T. Hence ac+c is joined
to at least d—e ( ^ 1) of the nodes ae+1, ae+2,..., ac_e_x, which number
c—2e—1, but it is not joined to two successive ones. It follows that there
are at least 2(d—e)—l ( > 1) of these nodes, so that c—2e—1 > 2(d—e)— 1
and therefore c > 2d. But if c > 2d then the graph is Hamiltonian because
it contains not more than 2d nodes, and this contradicts the assumption
that it is not Hamiltonian.
I t follows that e ^ d. But the graph contains at least c-\-e nodes and
c > d-\-1 by Theorem 2, so that if e > d the graph contains at least 2rf-f-1
nodes, and this contradicts the assumption that it contains at most 2d
nodes. This proves the theorem.
Theorem 3 is best possible and becomes false if the graph has 2d-{-1
nodes even when we impose the further condition that the graph has no
cut-node. This is illustrated by the following graph, which has 2d-\-l
nodes, satisfies the conditions of the theorem in other respects, and has
no cut-node:
The nodes of the graph are the 2d-\-l distinct nodes ax, a2, az,..., a2d+x,
every node with an even suffix is joined to every node with an odd suffix,
and two nodes with suffixes of the same parity are not joined by an edge.
In this graph the degree of the nodes with odd suffix is d and the degree
of the nodes with even suffix is d-\-l; the graph has no cut-node, but it is
not Hamiltonian. For it is clearly 2-chromatic, and therefore does not
contain a circuit of length 2d+l.
THEOREM 4. A connected graph which has no cut-node, in which the degree
of every node is at least d ( > 1) and which has at least 2d nodes contains a
circuit with not less than 2d edges.
We first prove the following
LEMMA 2. If x and y are two distinct nodes of a graph which has no
cut-node, and if W is any given path connecting x and y, then the graph
contains two paths connecting x and y and having the following properties:
(i) they have no node other than x and y in common; (ii) going along each of
 SOME THEOREMS ON ABSTRACT GRAPHS 73
them from x to y, the nodes of W occur in the same order as they do on W
going from x to y.
This is a strengthened form of Menger's theorem,! which establishes the
existence of paths having property (i).
It is convenient to introduce the following notation, which will be useful
elsewhere too. If "V is a path which contains the nodes g and h, the portion
of y which connects g and h will be denoted by ir{g,h). If g = h then
ir{g, h) means simply the node g. If the paths V and 'f" have one end
node in common, but are otherwise disjoint, then the path which consists
of V and ^ " together will be denoted by 'T'+'V".
To prove the lemma we use induction on the length of the given path W.
The lemma is clearly true for a pair of nodes for which the given path
consists of one edge. We assume that the lemma is true for any pair of
nodes if the length of the given path between them is at most n, and we
•will deduce that it is true for any pair of nodes if the length of the given
path between them isn-{-l.
Let a0 and an+1 be a pair of nodes joined by a path W whose nodes in
order are a0, av a2,..., an, an+J {n ^ 1). By hypothesis a0 and an are con-
nected by two paths Wx and W2 having the properties (i) they have no node
other than a0 and an in common, (ii) going along each of them from aQ to
an the nodes of W(a0, an) occur in the same order as they do going along W
from a0 to an. (One of them may, of course, be W(aQ,an) itself.) Now an
does not separate a0 and an+i, so there is a path connecting a0 and an+1
which does not go through an. This path has a part which connects one
of the nodes a0, aL,..., an_1, am say, with an+1 and has no other node from
among a0, av..., an_v We denote this part by if\ it is possible that iV*
coincides with a part of Wx or W2. Let ap (0 < p < m) be the node with
greatest suffix not greater than m along a0, ax,..., an_1 which belongs to
Wx or to W2, and suppose (without loss of generality) that it belongs to Wx,
then W2 has no node in common with W(ap,am). The nodes a0 and an+1
are therefore connected by the two paths
W1(a0,ap)+W(ap,am)+^ and W2+W(an,an+1),
and these paths satisfy the requirements of the lemma, which is therefore
proved.
From Lemma 2 we can immediately deduce the
COROLLARY. / / x is joined to a node z of W then the graph contains two
paths connecting x and y such that they have the properties (i) and (ii) and
one of them goes through z.
f Cf. G. Haj6s and D. Konig, op. cit.
74 G. A. DIRAC
To prove Theorem 4 itself we use induction on d. It is easy to see that
the theorem is true in the case d = 2. We will assume that it is true for
graphs in which the degree of every node is ^ d— 1 > 1 and deduce that
it is true for graphs in which the degree of every node is ^ d.
Suppose that it is not true, so that there is a graph F which satisfies
the conditions of the theorem but which contains no circuit of length ^ 2d.
By Theorem 1 the lengths of the paths contained in F are bounded. Let #
be one of the longest circuits in F and let the nodes of ^ in cyclic order be
av a2,..., ac, ax, where by hypothesis Id—2 < c < 2d— 1.
As in the proof of the preceding theorem it may be supposed that ac is
joined to a node of F which is not in ft, and it can be shown in the same
way as there that F contains a path ac, ac+v..., ac+e, where e ^ d, which
has no node except ac in common with the nodes of # , and which is among
the longest of all such paths in F. Then the only nodes to which ac+e
is joined are among ax, a2,..., ac,..., ac+e_x. Actually ac+e is joined only to
nodes from among ac, ac+l,..., ac+e_x. For if ac+e were joined to a node a{
of ^ with i ^ c, then ac and ai would divide <% into two arcs, one of which
would contain at least \c edges. This arc and the path ac, ac+x,..., ac+e, c^
together would make up a circuit with at least \c-\-d edges. But by
hypothesis d ^ i( c +*)> s o this circuit would contain more than c edges,
and # would not be one of the longest circuits in the graph. Hence ac+6 is
joined to d or more of the nodes ac, ac+v..., ac+e-x and to no others.
We denote d of the nodes to which ac+e is joined by aai, aai>..., a^, where
c ^ ax < a2 < ••• < ad a n ( i a i ^s chosen as small as possible. It will be
helpful to establish that:
If ax < j < c + e then aai and a5 are connected by a path of length ^ d
the nodes of which are a subset of the set
a
« « , . flo.,+1. —> c+e- (!)

Proof. Let <xh be such that och < j ^ ah+1, where 1 ^ h < d and where
aad+1 is to mean ac+e. Then aai and ai are connected by the path
W{aaii « a J+(a t t A , ae+e)+W{ac+e, af)
and this path goes through the d-\-l nodes a ai , aat,..., a w , ac+e.
Now it follows easily from Lemma 2 and the corollary that the graph
contains two paths O^ and "W% having the following properties: (i) iVx and
ifl each connect one of the nodes av a2,..., ac with one of the nodes
a
ai> aai+i»"-» ac+e a n d they have no intermediate node in common with
either of these two sets of nodes; (ii) #^ and *#£ have no node in common
except possibly ax; (iii) "Wx has aai as one of its end nodes. If c = ocx then
iVx reduces to the node ac. Further "Wx and "#£ do not both have ax as
end node, because if they did then one of them would contain no node
 SOME THEOREMS ON ABSTRACT GRAPHS 75
from among a2, a3,..., ac and so # would not be one of the longest circuits
in the graph. Hence iV[ and O^ are completely disjoint.
The two end nodes of ifx and #£ with suffixes < c divide c& into two
arcs, one of which contains at least d— 1 edges; we denote this arc by if'.
By (1) aax (which is one of the end nodes of #J) and the end node of O^
with suffix exceeding <xx are connected by a path of length ^ d the nodes
of which are a subset of the set aai, aai+1,..., ac+e>we denote this path by "W".
Then the paths if^, iV^ iV\ and iV" together constitute a circuit with at
least 2d nodes and edges, and this contradicts the hypothesis that the
graph has no circuit of length ^ 2d. This proves Theorem 4.
I am greatly indebted to the referee for his help in simplifying my
original proof of this theorem.
This theorem is best possible, as is shown by the following graphs, one
of which is finite, the other infinite.
(i) The graph consisting of the complete (d+l)-graphs T1} F2, r3,..., Tn
(n ^ 2) of which every pair have the same two nodes a and b in
common and are otherwise disjoint,
(ii) The graph consisting of an infinite set of complete (rf-fl)-graphs of
which every pair have the same two nodes a and b in common and
are otherwise disjoint.
It is noteworthy that in the second example the two nodes a and 6 are
of infinite degree, and in the first example the degrees of the two nodes a
and b tend to infinity with the order of the graph. This is an essential
feature of any such examples: in the following theorem we prove that for
connected graphs which have no cut-node and in which the degrees of the
nodes are bounded the length of the largest circuits tends to infinity with
the order.
THEOKEM 5. The length of one of the longest circuits necessarily contained
in a connected graph of order n without a cut-node tends to infinity with n
provided the degree of every node remains bounded for all n.
Proof. Let l(n, d) denote the length of one of the longest paths necessarily
contained in a connected graph of order n without a cut-node in which the
degree of every node is at most d. Then if d is fixed, l(n, d) tends to infinity
with n.
For suppose that in such a graph the length of a longest path is ^ L,
and let a denote any chosen node of the graph. The number of nodes at
a distance 1 from a is at most d, the number of nodes at a distance 2 from
a is at most d2,..., the number of nodes at a distance L from a is at most dL.
The graph contains no path of length exceeding L, so that the number of
nodes in the graph is at most 1 -f- d -f d2 -f... -f dL. Hence given any integer L,
76 G. A. DIRAC
l(n,d) > L for all n > i+d+dz+...+dL. Thus if dis fixed l(n,d) tends
to infinity with n.
By Theorem 1 a graph of order n without a cut-node in which the
degree of every node is at most d contains a circuit of length exceeding
J{2l(n, d)}. This proves Theorem 5.
The requirement that the degrees of the nodes should remain bounded
is essential. This is illustrated by the examples after Theorem 4 and also
by the following graph: The nodes of the graph are a, b, av a2, az,..., alh
(n > 2) and the edges are {a,ax), (a,a2),..., (a,an), (Mi), (M 2 )»-. ( M J -
The graph contains only circuits of length 4 however large n may be. It
is easy to see, of course, that a graph of order ^ 4 without a cut-node
always contains a circuit of length ^ 4.

II
If a graph is not connected, its chromatic number is the greatest number
among the set of chromatic numbers of its connected components. Accord-
ingly a graph of chromatic number k has at least one connected component
with the same chromatic number, so that, if we wish to find relations
between the chromatic number of a graph and the lengths of the circuits
contained in it, we may confine ourselves to connected graphs.
De Bruijnf has proved that an infinite k-chromatic graph contains a finite
k-chromatic subgraph. Accordingly we may confine ourselves to finite
connected graphs.
In what follows the following notations and definitions will be useful:
If the node a belongs to the graph F (in symbols: if a e F), the graph
obtained from F by deleting a and all edges adjoint to a, leaving all
other nodes and edges unchanged, will be denoted by F—a. Similarly if
a, &,..., c e F, the graph obtained from F by deleting a, 6,..., c and all edges
incident with at least one of them will be denoted by F—a—b~...—c.
The chromatic number of a graph F will be denoted by K{T).
If a G F and K(Y—a) < K(Y) we call a a critical node of F. Clearly if a
is critical then K(Y—a) = K(T)— 1 and the degree of a is at least K(T)—l.
If every node of F is critical we say that F is a critical graph. It follows
from the preceding remarks that a critical graph is finite and connected.
Now suppose that F is a ^-chromatic graph. If F is infinite, by de Bruijn's
theorem it contains a finite ^-chromatic subgraph F'. If F is finite we may
suppose F = F'. If F' is not critical, it has a node a which is not critical,
and T'—a is also ^-chromatic. If T'—a is not critical, it has a non-critical
node 6 so that Y'—a—b is also ^-chromatic. By successively deleting
f Unpublished.
 SOME THEOREMS ON ABSTRACT GRAPHS 77
non-critical nodes in this way after a finite number of steps we obtain a
Critical ^-chromatic graph F". Hence
A k-chromatic graph contains a critical k-chromatic subgraph. (1)
A critical graph is more sharply defined and less arbitrary than a non-
critical one. (N.B. If the graph F is not critical, it may contain more than
one critical subgraph of the same chromatic number. The successive
removing of nodes and edges is not necessarily a unique process.)
A colouring of a graph F using at most k colours is a function C defined
over the nodes of F and taking one of the values 1, 2,..., k at each node
with the condition that C(x) ^ C{y) if x and y are joined by an edge.
Such a colouring will also be called a ^-colouring of F.
Examples of critical graphs. A critical 1-chromatic graph is simply a
node by itself. A critical 2-chromatic graph consists of two nodes joined
by an edge. A critical 3-chromatic graph consists of a circuit with an odd
number of nodes and edges. This last statement follows from a result due
to Kdnig.f The chromatic number of a graph is < 2 if and only if it has
no circuit with an odd number of nodes and edges.
The following characteristic of critical graphs is important:
LEMMA 3. A critical graph has no cut-node.
Proof. It is obvious that critical 1 — and 2— chromatic graphs have no
cut-node. Suppose the lemma false, so that there is a ^-chromatic critical
graph F with k ^ 3 which has a cut-node a.
The graph Y—a is disconnected and has n (n > 2) mutually disjoint
connected components. Let us denote these by

where the nodes in the bracket are the nodes in the connected components.
Let
FJL = [a,a11,a12,...,a1(X\, F 2 = [a, a21) a 2 2 , . . . , a 2 p ] , •••> I » == \.a>ani>an'&>-
where Tv F2,..., Fn are defined in the obvious way, namely (a, a^) e F^ if
and only if {a,ai:j) e F for i = 1, 2,..., n. By hypothesis F is critical so
#(I\) < k— 1. Let Ci be a (k— l)-colouring of F; with C^a) = 1 for
1 < i < n. Define C over the nodes of F as follows:
C(a) = 1, darf - Gifa,).
Then C represents a colouring of F using at most k— 1 colours, winch
contradicts the assumption that F is ^-chromatic. Thus the lemma is
proved.
f D. Konig, op. cit. 170.
78 G. A. DIRAC
Because of these characteristics of criticalfc-chromaticgraphs, Theorems
2, 3, 4, and 5 of Part I of this paper immediately lead to new results:
(i) From Theorem 2 it follows that:
/ / k ^ 3 a k-chromatic graph contains a circuit of length at least k. (2)
For a ^-chromatic graph with k > 3 contains a critical fc-chromatic sub-
graph which is finite and in which the degree of every node is ^ k— 1 ^ 2.
Now (2) follows from Theorem 2 by substituting d = k— 1.
(ii) From Theorem 3 it follows similarly that:
/ / k ^ 3 a critical k-chromatic graph of order at most 2k—2
is Hamiltonian, (3)
i.e.
If k ^ 3 a k-chromatic graph of order at most 2k—2
contains a k-chromatic Hamiltonian subgraph. (3')
(iii) From Theorem 4 it follows likewise that:
/ / k ^ 3 a critical k-chromatic graph of order at least 2k—2
contains a circuit of length at least 2k—2, (4)
i.e.
If k ^ 3 a k-chromatic graph either contains a k-chromatic
Hamiltonian subgraph or a circuit of length at least 2k—2. (4')
(iv) Finally from Theorem 5 it follows that:
/ / k ^ 3 the length of one of the longest circuits necessarily con-
tained in a critical k-chromatic graph of order n tends to infinity
with n provided the degree of every node remains bounded for all n. (5)
The results (2) and (3) or (3') will be improved somewhat by exploiting
the jfc-chromatic property more fully. In place of (2) we can prove the
following:
THEOREM 6. Ifk^3,a k-chromatic graph contains as a subgraph either
a complete k-graph or a circuit of length at least k+2.
Proof. The theorem is true for 3-chromatic graphs because a complete
3-graph is a circuit with 3 edges and a 3-chromatic graph contains a
circuit with an odd number of edges.f To prove it for k > 4 it is, by (3) and
(4), sufficient to prove that a k-chromatic graph either contains a complete
k-graph as a subgraph or has at least k-{-2 nodes.
A ^-chromatic graph of order k-\-1 can be obtained from a complete
(&+l)-graph by deleting edges from this complete (&-{-l)-graph. Let
f D. Konig, op. cit. 170.
 SOME THEOREMS ON ABSTRACT GRAPHS 79
av a2,..., ak, ak+x be the nodes of a complete (&-|-l)-graph F. If we delete
an edge, the edge (ak, ak+1) say, the remaining graph F' is ^-chromatic and
contains the complete ^-graphs [ax,a2,...,ak] and [ax,a2,...,ak_x,ak+1]. If
we now delete either (a) any edge («*,%) with i, j < k— 1, or (6) an edge
incident with ak and an edge incident with ak+1, the remaining graph is
(k—l)-chromatic. If we delete edges in such a way that we do neither (a)
nor (6), then the remaining graph will contain a complete &-graph as a
subgraph. Hence a ^-chromatic graph of order k-\-1 contains a complete
&-graph as a subgraph, and the theorem is proved.
Theorem 6 is best possible; we can construct a ^-chromatic graph of
order k-\-2 (k ^ 3) which does not contain a complete &-graph as a sub-
graph as follows. The graph contains the nodes ax, a2, a3,..., ak_x, bx, b2, 63.
Every pair of distinct nodes from among ax, a2, a3,..., ak_x is joined by an
edge. bx is joined to a2, a3,..., ak_x; b2 is joined to ax, a3, a4,..., ak_x; 63 is
joined to a3, a4,..., ak_x, bv b2. It is easy to see that this graph has the
required properties.
To prove Theorem 6 we proved that a jfc-chromatic graph contains a
complete &-graph as a subgraph or has at least &-{-2 nodes. This can
be generalized quite easily as follows:
THEOBEM 7. / / 0 < n ^ k— 1 a k-chromatic graph either contains a
complete (k—n)-graph as a subgraph or has at least k-\-n-\-2 nodes.
Theorem 6 is a special case of Theorem 7 obtained by substituting n = 0.
Proof of Theorem 7. Suppose the graph F contains a complete (k—n—1)-
graph I" but no complete (k— %)-graph as a subgraph, where 0 < n < k—3.
By Theorem 6 we need at least three more nodes to construct a critical
(k—w)-chromatic graph r o from V so that Fo should not contain a complete
(k—w)-graph as a subgraph. Next, we need at least two more nodes to
construct a critical (k—w+l)-chromatic graph I\ from Fo so that Fx should
not contain a complete (k—w)-graph as a subgraph. For in order to
construct a (k—w+l)-chromatic graph from the critical (k—n)-chromatic
graph Fo using only one more node we must join this node to every node
of Fo. (Because if the new node x is not joined to the node y of Fo, the
new graph can be coloured with k—n colours by colouring Fo—y with
k—n—1 colours, which can be done because Fo is critical, and then giving
x and y both the same new colour.) But Fo contains a complete (k—n— 1)-
graph so that we must inevitably construct a complete (k—n) -graph in the
process. Similarly we need at least two more nodes to construct a critical
(k—n-j-2)-chromatic graph F2 from Vx so that F2 should not contain a
complete (k—w)-graph, and so on until we have constructed a ^-chromatic
graph Yn. Now F contains a succession of such critical graphs; it therefore
 80 G. A. DIRAC
follows that F has at least k—n—\-\-Z-\-2n = k-\-n-\-2 nodes. This proves
Theorem 7.
Theorem 7 is, of course, not best possible. For example there are
^-chromatic graphs which contain no complete 3-graph as a subgraph, but
they have many more than 2k—I nodes as k becomes large.
The following is an improvement on (3):
THEOREM 8. / / k ^ 3 a critical k-chromatic graph of order <! 2k— 1 is
Hamiltonian.
Proof. Suppose that the theorem is false, and let F be a critical k-
chromatic graph of order 2k— 1 which is not Hamiltonian. Then F has
no cut-node and the degree of every node is at least k— 1, so by Theorem 4
F contains a circuit ^ with 2k—2 edges. Let the nodes of this circuit in
cyclic order be av a2, a3,..., «2fc-2> ai> an( ^ ^ * n e remaining node be
denoted by a2k_v
The degree of the node a2fe-i is at least k—l. It is not joined to two
consecutive nodes of ^ , so it is joined to every alternate node. Suppose it is
joined to all the nodes with even suffix.
Two nodes with an odd suffix are not joined by an edge. For suppose
two nodes with odd suffixes were joined by an edge, and suppose (without
loss of generality) that one of them is av and the other ait where
3 < i < 2&-3.
Then the graph contains the circuit whose nodes in cyclic order are:
«i» a2> a3>—» ai-i> a
2*-i> a2fc-2> a2fc-3>-••> ai+i> a i> ai> an(
* ^18 circuit embraces
all the nodes, so that the graph is Hamiltonian, contrary to hypothesis.
Let F' denote F—ax—a3—ab—...—«2&-i- Then V contains the k~ 1
nodes of even suffix and all edges joining them in F. Now K(V) < k—2
because if K(V) = k—1 then F' is a complete (k—l)-graph, and since
a
2i-i ^s j ° m e d to all the nodes of F' this implies that F contains a complete
fc-graph as a subgraph, whereas F was to be critical. Since no two nodes
with odd suffixes are joined by an edge, F can be coloured by first colouring
F' and then giving all the nodes with odd suffix the same colour, one which
is not used in colouring F'. Because ^(F') ^ k—2, V can thus be coloured
using at most k—l colours. This contradicts the datum that F is k-
chromatic, and the theorem is proved.
It seems very likely that Theorem 8 remains true even if the orders of
the graphs may be considerably greater than 2k— 1. In fact it seems safe
to conjecture that:
If k ^ 3, a critical k-chromatic graph of order ^ Bk2 is Hamiltonian,
B being a positive constant.
 SOME THEOREMS ON ABSTRACT GRAPHS 81
If k — 4 it may even be the case that all the critical graphs are
Hamiltonian. But, while I can improve Theorem 8 by an increase of 1 in
the order, to prove anything like this seems very difficult.
I think also that (4) and (5) are very far from strong enough and believe
that if k ^ 3, a critical k-chromatic graph of order n contains a circuit of
length > A{k)n-, A{k) being a positive constant depending on k.
However, I cannot even prove (5) without the restriction on the degrees
of the nodes.
King's College,
London, W.C. 2.

5388.3.2