―Evolution‖ by vertex of even-order regular graphs
`Tamás Dénes
`
`
`
`In graph theory circles, it is generally interesting to examine a structurally similar problem, but
`from a different point of view, to see alternate forms of graphs under certain transformations.
`For example, Γn, the n-vertex complete graph, can be constructed from Γn-1, the complete graph
`on n-1 vertices, by adding a vertex and connecting it to each vertex of Γn-1. The same transformation on
`any other regular graph of other degree does not achieve the goal. al rd s and lfr d nyi addressed
`graph evolution in [3] from another perspective.
`In the present work we are only concerned with undirected, even-order regular graphs.
`In the first section of this paper we define the evolutionary transformation and prove several
`related theorems. The second and third sections concern graphs for which the transformation cannot be
`applied.
`
`Definition 1. Let Γ = ( ,E) be an n-vertex simple graph and pi ∈P, pj ∈P be neighboring vertices, and p
`be a vertex which is a neighbor to neither pi nor pj . (P and E represent the sets of vertices and edges of the
`graph Γ.)
`We take the EC transformation on vertex p to be the following:
`(1) EC: E → E’

` E’ = E \ {(pipj)}  {(ppi), (ppj)}
`where
`
`Herein we designate the set of all even regular graphs using as PR and the sets of all 2, 4, ..., k
`(k even) order regular graphs as PR2, PR4, ..., PRk. Then the following must be the case:
`
`1. PR = PR2  PR4  ...  PRk  ...
`2. ∀i  j, (i, j even), PRi ∩ PRj =
`3. ∀Γn,k ∈ PRk, ∃! PRk: Γn,k ∈ PRk ; that is, the set PR has a classification.
`
`Definition 2. Let Γn,k ∈ PRk be an n(cid:173)vertex, k(cid:173)regular graph. Further suppose Γn,k = (P,E) and Γn+1 =
`(P  {p}, E’), where p  P.
`
`
`We take the ET transformation on vertex p to be the k/2 EC transformation on vertex p, that is, let (p1p2),
`(p3p4), ..., (pk-1pk) be edges in Γn,k , then
`
`(2)
`
`
`ET: Γn,k → Γn
`
`Mathematical Proceedings
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` [page 365]
`
`
`where E’ = E \ { (p1p2), (p3p4), ... , (pk-1pk) }  { (pp1),(pp2), ... , (ppk) }
`
`Theorem 1. Let k be an even number. The ET transformation can be used for every Γn,k ∈ PRk .
`
`
`
` OOF. It is sufficient if we observe that in every Γn,k there exist k/2 independent edges. For the proof
`we use the following theorem from G. A. Dirac [2]:
`
`―If in a simple graph every vertex has degree of at least r (r > 1), then there exists a cycle in the
`graph of length at least r + 1.‖
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1017, p. 1 of 13
`
`

`
`
`If we take K to be a cycle of length k+1 in Γn,k (one certainly exists on the basis of the theorem cited),
`then using the method illustrated in figure 1 to select the edges (p1p2), (p3p4), ... , (pk-1pk) we get a set of
`exactly k/2 unconnected edges.
`
`
`
`
`
` Figure 1
`
`Definition 3. Let Γn,k = (P,E) PRk, p P, and we take the vertex pairs p1p2, p3p4, ..., pk-1pk to be
`neighbors of p but pairwise not neighbors. Then we take the ET transformation to be:
`
`(3) ET-1: Γn,k → Γn-1 = ( ’, E’), ’ = P \ {p}
` E’ = E \ { (pp1), (pp2), …, (ppk)  { (p1p2),(p3p4), …,(pk-1pk) }
`
`
`
`
`
`
`Definition 4. Let Γn,k = (P, E) be a graph on n vertices, p P, and q1, q2, ... , qr be neighbors of p in Γn.
`Then we take the subgraph of Γn generated by p (designate this Gp = ( ’, E’) ), and it turns out this is the
`subgraph where ’ = {q1, q2, ..., qr} and (qi, qj) E′ ⇔ (qi, qj) E .
`
`Definition 5. Let Γn PR and p Γn . Then the vertex p is T(cid:173)characterized if the complement of the
`subgraph on Γn generated by it contains a 1-factor.
`
`Theorem 2. The ET-1 transformation can be applied to a graph Γn,k = (P,K) PRk if and only if there
`exists a T-characterized vertex p Γn,k .
`
`PROOF. Necessity: From the definition of ET-1 it follows that there exists p∈ Γn,k from which we can
`select neighbors p1p2, p3p4, ... , pk-1pk which are pairwise not neighbors. In the complement of the
`subgraph on Γn constructed on p1, p2, ... , pk they will be neighbors, and they comprise a 1(cid:173)factor, as any
`two vertex pairs have no common vertex. This is precisely what it means for the vertex p to be
`T(cid:173)characterized.

`
`Sufficiency: The proof in this direction is the exactly the reverse of the above necessity proof.
`
`Theorem 3. For every even k ≥ 4 there is a graph Γn,k PRk which has no vertex p which is
`T(cid:173)characterized.
`
`Equivalent formulation: For every even k ≥ 4 there exists a graph Γn,k PRk for which no graph
`Γn-1,k ∈ PRk can be constructed with the ET transformation.
`
`
`
` OOF. Let k be an arbitrary even number, k ≥ 4. Let us examine two complete graphs on k+1 vertices
`k+1,k = (P1, E2) and Γ2
`Γ1
`k+1,k = (P2, E2). Let (pi1, pj1) E1 and (pi2, pj2) E. Then we construct the following
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1017, p. 2 of 13
`
`

`
`graph Γn,k = (P , E)
`
`
`
`
`
`
`
`
`
`
`Figure 2
`
`
`
`
`We will demonstrate that Γn,k constructed in this way has does not have a T(cid:173)characterized vertex.
` s every graph Γn,k constructed in this way is symmetric, for the proof it is enough to
`demonstrate for each vertex of the subgraph (for example Γ1
`k+1,k). Here we can differentiate between two
`cases of selected pairs of vertices:
`
`
`a) pi1, pj1
`b) any other pair

`
`A1 = P1  {pi2} \ {pi1}
`B1 = E1 \ { (pi2pr) | ∀ pr ∈ P1 \ {pi1} }
`
`A’1 = A1
`B’1 = E1 \ { (pi2ps) | ∀ps ∈ P1 \{pi1} }
`
`
`For the case in a), we take G1 = (A1, B1) to be the subgraph constructed on neighbors of p i1. Then:
`
`(6)
`(7)
`
`So the complement ̅1 = ( ’1, B’1) is therefore the following:
`
`(8)
`(9)
`
`So ̅1 does not contain a 1(cid:173)factor, that is, p is not T(cid:173)characterized (and similarly pi2, pj1, … , pj2). For the
`case in b), let p ∈P1, p  pi1  pj1, and G2 = (A2, B2) be the subgraph constructed on the neighbors of p:
`
`(10) A2 = P1 \ {p}
`(11) B2 = E2 \ { ( pi1pj1), (ppr) | ∀ pr ∈ P1 \ { p } }
`
`Then ̅2 = ( ’, B’) will be the following:
`
`(12) ’2 = A2
`(13) B’2 = { ( pi1pj1 ) }
`
`So ̅2 does not contain a 1(cid:173)factor, that is, no vertex in case b) is T(cid:173)characterized. And so the 2 theorem is
`proved.

`
`
`
`
`P = P1  P2
`E = E1  E2 \ { (pi1, pj1), (pi2, pj2) }  { (pi1, pi2), (pj1, pj2) }}
`
`
`
`
`
`
`
`
`
`
`
` [page 366]
`
`
`(4)
`(5)
`
`The graph Γn,k where for k = 4 is illustrated in figure 2.
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1017, p. 3 of 13
`
`

`
`In figure 3/a(cid:173)d the graphs G1, ̅1, G2, ̅2 are illustrated for k = 4. (The bolded edges and vertices
`belong to the corresponding graphs.)
`
`
`Figure 3
`
`
`
`
`6. Definition. We define a Vertex Prime (VP) graph as a graph in PR which contains T(cid:173)characterized
`vertex.
`
`Then Theorem 3 can be formulated as follows: Each of the classes of graphs PR4, PR6, ... , PRk, ...
`contains a VP graph.
`
`In the following we examine the cases under which a vertex is not T(cid:173)characterized. We take advantage of
`the following well-known result [1].
`
`
`
`Lemma 1. complete graph Γn (where n is even) can be expanded into n(cid:173)1 one-degree factors. 

`
`Theorem 4. Let Γn,k ∈ PRk and p ∈ Γn,k = (P, E) . If p is not T(cid:173)characterized, then there exist at least
`k(cid:173)1 cycles of length 3 which contain p.
`
`
`
`
`
`
`
`
`
` [page 367]
`
`
`
`
`
`
`
`
`
`
`
`
`
`PROOF. If p is not T-characterized, then the complement of the subgraph of Γn,k generated by it (G =
`(A,B)) does not contain 1(cid:173)factor. By Lemma 1, ̅ ontains n(cid:173)1 edge(cid:173)independent 1(cid:173)factors, and in G from
`these factors an edge must exist such that in ̅ they are not a 1(cid:173)factor. So the number of edges in G is at
`least k(cid:173)1. As it is the case in G that every edge endpoint is a neighbor of p, a 3(cid:173)cycle containing p is thus
`constructed. And hence the theorem is proved.
`
`For k = 4, the following illustrations in figure 4/a(cid:173)h depict cases where the vertex p is not T(cid:173)characterized
`(bold edges indicate ̅ ).
`
`Lemma 2. Let Γn be an n(cid:173)vertex complete graph (n an even number) and we denote the number of all
`1-factors of Γn as F. Then
`
`
`)
`
`
`
`
`
`(
`
`
`
`)
`
`
`
`) (
`
`
`
`(
`
`)(
`
`(14)
`
`Fn =
`
`
`PROOF. It is easy to see that the assertion is true for the case n = 2. Suppose it also holds for any
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1017, p. 4 of 13
`
`

`
`k n – 2, that is:
`
`
`)
`
`
`
`
`) (
`
`
`)(
`
`(
`
`
`
`)
`
`
`
`(
`
`(15)
`
`Fk =
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` [page 368]
`
`Figure 4
`
`
`Then Γk has two vertices beyond which k+1 new vertex pairs can be selected (we don’t take note of the
`ordering of the two points), each of which has an F
` numbered 1(cid:173)factor which each share exactly one
`
`
`
`k
`
`(16) Fk+2 = ( k + 1 ) ∙ F k
`
`edge, so
`
`
`
`Recalling that
`
`
`)
`
`
`(
`
`
`
`
` ( )
` =
` = k + 1
` ( )
`
`(17)
`
`
`So thus
`
`
`)
`
`
`
`
`) (
`
`
`
`)(
`
`
`
`
`
`
`
`
`)
`(
` =
`
`
`
`) (
`
`
`
`
`
`
`)(
`
`(
`
`
`
`
`
`)
`
`
`(
`
`
`
`
` *
`
`(18) Fk+2 =
`
`
`This concludes the proof of the theorem.

`
`Corollary.
`
`4. In the context of (16) we can write Fn recursively as follows:
`
`
`(19) Fn = (n - 1) ∙ Fn-2

`
`2. The proof of Lemma 2 shows that if e is an edge contained in an E 1(cid:173)factor of Γn, then exactly Fn-2 such
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1017, p. 5 of 13
`
`

`
`1(cid:173)factors are in Γn which with E contain exactly the ei shared edges.
`
`3.If the number of distinct 1(cid:173)factors in Γn is denoted FDn, then based on Lemma 1 and (19) we have:
`
`FDn = Fn ⇔ n-1 = (n(cid:173)1) ∙Fn-2 ⇒ 1=Fn-2 ⇒ n=4
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` [page 369]
`
`
`4. The correspondence to (14) can be simplified by hiding the numerator as follows:
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` =
`
`( )
` ( )
`
`
`
`
`
`
` ( )
`
`Fn =
`
`
`
`E = { E1, E2, … , Em }
`
`
`Definition 7. Let Γn be a graph with n vertices and let
`
`(20)
`
`be a set of 1-factors of Γn and e1, e2 , …, ep be edges of Γn.
`
`We say the edges e1, e2 , …, ep are a representation of E if every 1-factor of E shares at least one
`edge with { e1, e2 , …, ep }.
`
`Lemma 3. Let Γn be a complete graph (n even). Denote the set of all 1-factors of Γn as
`
`(21) E = { E1, E2, ... , Er} where r = Fn and 

`
`(22) R = { e1, e2 , …, en-1} 

`
` a
`
` set of edges of Γn. Then R is a representation of E if and only if for any two ei  ej , there does not exist
`Ek E for which ei E and ej E .
`
`PROOF. Necessity: Suppose that R is a representation of E and there exist ei  ej and Ek where ei Ek and
`ej ∈ Ek . On the basis of Lemma 2, Corollary 2, ei represents an Fn-2 1(cid:173)factor of E, and ej does also. As
`both edges are in Ek, it is the case that the for the 1(cid:173)factor Kij represented by the two edges, it holds that

`
`(23) Kij < 2 ∙ Fn-2
`
`If we suppose that the remaining n(cid:173)3 edges in R represent the maximum n(cid:173)1 1(cid:173)factors, then it is the case
`that for the K E, the elements of E represented by R, it holds that
`
`(24) KE < (n-1) ∙ Fn-2
`
`which is a contradiction, as the number of elements in E is (n - 1) ∙ Fn-2 and R is a representation
`of E, so for KE the equality must hold.
`
`Sufficiency: As every Ek E 1(cid:173)factor contains only one edge ei R, and on the basis of Lemma 2,
`Corollary 2, an edge ei represents an Fn-2 1-factor of E, since there are n-1 of numbering (n - 1) ∙ Fn-2,
`this is all of the edges of E.
`We have proved the theorem.
`
`
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1017, p. 6 of 13
`
`

`
`Theorem 5. For a complete graph Γn (n > 4, even), all 1(cid:173)factors can be represented by exactly n(cid:173)1 edges if
`and only if those edges are joined by a vertex.
`
`PROOF. Necessity: Let p ∈ Γn be such a vertex. s every 1-factor of Γn is contained by an edge attached
`to p, it follows that all such edges are indeed an n-1 element representation of all 1-factors of Γn .
`
`
`Sufficiency: Let us examine an arbitrary edge (p1p2) ∈ Γn (p1 and p2 are the endpoints of edge ei). Let this
`be the first element of the n(cid:173)1 element representation. By Lemma 3, the second element can only be
`selected from amongst such ej for which the only 1(cid:173)factor containing ei does not also appear.
`
`
`
`It is easy to see that such an edge can only be selected from those which have p1 or p2 as an endpoint. (See
`figure 5.) (The dark thick lines are edges that may be chosen.)
`Suppose that we choose (p1p3) = ej as the second element of the representation (see figure 6.)
`Continuing according to Lemma 3, we may choose from amongst p1 and p2 for attaching (that
`which can still be chosen), and immediately for the e1 edge we can also take advantage of Lemma 3,
`
`
`
`
`
`
`
`
`
` [page 370]
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` Figure 5
`
`
`
`
`
` Figure 6
`
`
`
`thus the desired representation for p3 must attach. Such an edge could only be (p2p3). With this, the edges
`which can be chosen have been consumed. Thus this selection constitutes a representation if and only if
`n=4; for all other cases the n(cid:173)1 edges which can be selected as the elements of the representation are
`attached to p1 (thus necessitating the condition that n>4). We have thus proved the theorem. For n=4 the
`entire representation is depicted in figure 4.
`
`In the remainder of the paper we introduce a type of graph which under a certain set of assumptions
`proves to be a VP graph. We will examine, for a given even number k, what the smallest number n is such
`that Γn,k PRk is a VP graph.
`Denote by C the set of all complete graphs where the elements are C1, C2, ... , Cn. (Cn is the
`complete graph of n vertices.)
`
`Definition 8. Let Ci1, Ci2, ... , Cit be (not necessarily distinct) graphs in C where Cij = (Pj, Ej) and
`j= 1, 2, ..., t. The t(cid:173)composition of graphs Ci1, Ci2, ... , Cit (indicated by ―t‖) is a graph Γ = (P , E) where
`the following are true:
`
`(a)
`(b)
`(c)
`
`
`Γ is a regular graph
`P = P1 P2 ... Pt , ∀i  j: Pi  Pj =
`E = E1 E2 ... Et E’, ∀I  j: Ei  Ej = where E’ is the set of so-called connector edges.
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1017, p. 7 of 13
`
`

`
`COMMENTS.
`1. The set E’ of edges is not easily determined.
`2. E’ determines the connectedness of the graph Γ. That is, if E’ = , then Γ is a t-component regular
`graph from complete subgraphs and i1 = i2 = .... = it.
`3. If Γ = Γn,k and max(i1, i2, ..., it ) = L, then L ≤ k+1.

`
`Theorem 6. Let Γn = (P, E) be a connected graph on n vertices. If in ̅n there exists a complete subgraph
`]+ 1 vertices, then in Γn there is no 1(cid:173)factor. (We will use ̅n to indicate the graph complement of Γn.)
`on [
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` [page 371]
`
`
`
`
`
`
`
`
`
`|P′| = [
`
`
`
` OOF. Let G = ( ’, E’) be an [
`] + 1 vertex complete subgraph. Then
`] + 1 ⇒ |P ∖ P′| = [
`] if n odd or
` = [
`]-1 if n even.
`In ̅n the vertices of ’ can only be connected to vertices of \ ’, so certainly in ’ there is at least one
`vertex which has no pair in P \ ’, that is, Γn does not contain a 1(cid:173)factor.
`
`Theorem 7. Let Γn,k PR and k ≥ 4. Further suppose the following:
`1. Cij C , j=1,2,...,t ≥2.
`2. Γn,k is the t(cid:173)composition of Ci1, Ci2, ..., Cit
`
`3.
` ≤ ij ≤ k j =1,2,...,t ≥ 2
`
`Then Γn,k is a VP graph.
`
`
`
` OOF. We shall examine an arbitrary vertex p in Γn,k . Then from property b) of the t(cid:173)composition, it
`follows that there exists Cij in Γ where p ∈ Cij and ij fulfills the conditions of Theorem 3. If we now
`examine the subgraph of Γn,k generated by p, there are k vertices and it contains Cij, which fulfills the
`
`conditions for Theorem 6 because
` ≤ i ≤ k. That is, the complement of the subgraph generated by p
`
`does not contain a 1(cid:173)factor. This means that p is not T(cid:173)characterized. As we did not connect an edge to p,
`it can be done to any vertex in Γn,k , so Γn,k is a VP graph.
`
` A
`
` graph meeting conditions 1, 2, and 3 is shown in Figure 7.
`
`Figure 7
`
`
`
`
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1017, p. 8 of 13
`
`

`
`
`COMMENTS.

`1. From the proof of Theorem 7 it easily follows that to the extent that in Γn,k there are
`subgraphs Cij ∈ C, where ij =
` + 1, then Γ is not a V graph. Such a graph is shown in figure 8.
`2. Theorem 7 also addresses the statement of Theorem 3, thus we now know that the VP graphs
`constructed in Theorem 3 are not the only to exist for any even number k.
`3. If we examine for the minimum case the first and third suppositions for Theorem 7, then we have t=2
`
`and i1 = i2 = .
` , and we get that the number of vertices is n = k + 4 for the t(cid:173)composition of Ci1 and Ci2
`
`= Γn,k VP graph.
`
`
`
`From this follows the following theorem: 

`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` [page 372]
`
`
`
`
`
`Figure 8
`
`
`
`
`Theorem 8. For any even number k ≥ 4 there exists a Γn,k VP graph where n = k + 4.
`
`
` s an example, in figure 9 we can see a Γ8,4 graph. s we know, for any Γn,k PR where n ≥ k +
`1 and Γk+1.k is complete there is no VP graph, so the question arises, for the given k cases, what is the
`smallest nmin number for which there exists Γn,k PR a VP graph.
`
`Taking into account Theorem 8, it follows that
`
`(25)
`
`9.Theorem. If Γ PR and n = k+2, then Γ is not a VP graph.
`
`PROOF. The proof can be completed using total induction on the degree. In figure 10 the case of k=2 is
`depicted, for which explanation can be seen clearly.
`
`k+2 ≤ mmin ≤ k + 4
`
`
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1017, p. 9 of 13
`
`

`
`Figure 9
`
`
`
`
`
`
`
` Figure 10
`
`
`
`
`Suppose that the statement is true for Γ. We examine a Γ PR graph where n = k + 2 and select from
`these an arbitrary vertex p. Then it is easy to see that Γn,k contains exactly one other vertex q which has
`the same neighbors as p, that is, the subgraphs generated by p and q are the same (see figure 11).
Denote
`as Gp the subgraph of Γn,k generated by p (also by q). Gp has exactly k vertices, is a degree k (cid:173) 2 regular
`graph, which on the basis of the inductive assumption meets the conditions of the assertion, that Gp is a
`VP graph.
`Based on this we can select any vertex of Gp, (let us call it z), and in the complement of the
`subgraph of G (G’) generated by it there is a 1-factor. Denote as G the subgraph of Γ generated by z. Then
`Gz exactly contains the points p and q outside the points in G’p, so ̅
`z contains the pq edge, so this
`establishes that there is a 1(cid:173)factor of ̅′p and (pq) is precisely a 1(cid:173)factor of ̅z, so the vertex z is
`T-characterized and Γn,k is not a VP graph.
`With this we have proved the theorem.
` s an example in figure 12 we can see a Γ8,6 graph, which using the symbols from Theorem 9, we
`indicate (in bold) the Gz 1(cid:173)factor for the vertex z.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` [page 373]
`
`Figure 11
`
`
`
`
`
`Figure 12
`
`
`
`
`10.Theorem. For any case k ≥2, there exist Γn,k k-regular graphs for which n = k +3 and Γn,k does not
`contain a 1(cid:173)factor.
`
`
`
` OOF. If k ≥ 3, then we can examine the vertex set on n vertices and select from these three vertices
`we label p1, p2, and p3. Now if we connect p1, p2, and p3 in order to the remaining vertices of P \ {p1, p2,
`p3} as in figure 13, then the degree of these three vertices will be exactly k = n (cid:173) 3, while the degree of
`every other vertex in P \ {p1, p2, p3} is exactly 3. We denote the graph arising from this G1.
`Now from the vertices in P \ {p1, p2, p3} we create an arbitrary regular graph of degree k(cid:173)3 which
`we denote as G2. If the graphs G1 and G2 intersect, we get a k = n (cid:173) 3 degree regular Γn,k graph. We create
`a ̅
`n,k graph. Due to the above construction, the points in {p1, p2, p3} in the general case will not be
`
`
`neighbors to the vertices in P \ {p1, p2 ,p3} of ̅n,k . That is, ̅n,k splits into two components, for which the
`portion containing the vertices p1, p2, and p3 does not contain a 1(cid:173)factor, independent of whether k is even
`or odd. Thus ̅
`n,k does not contain a 1(cid:173)factor.

`If k = 2, then n = 5, in which case due to being an odd number Γn,k does not contain a 1(cid:173)factor.
`With this the theorem is proved.

`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1017, p. 10 of 13
`
`

`
`It is easy to see that if k = 1 and n = 4 the theorem does not hold.
The well(cid:173)known Kuratowski
`graph is achieved in the theorem construction for the case k = 3, see figure 14.
`
`
`
`Figure 13
`
`
`
`
`
`
`
`Figure 14
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The following theorem gives a method for further specifying the inequality in (25), allowing a specific
`determination of the value of nmin.
`
`Theorem 11. For any even k ≥ 6, there exists a Γ ∈PR VP graph where n = k +3.
`
`
`
`
`
`
`
`
`
` [page 374]
`
`
`
` OOF. Let Γn,k be a graph arising from the construction in the proof of Theorem 10 (see the figure in
`13) with the restriction (using the symbols from Theorem 10) that the G2 subgraph should not contain a
`1(cid:173)factor. By Theorem 10 we assume that one such G2 always exists. We show that every vertex of Γn,k is
`T(cid:173)characterized.

`Further suppose p is an arbitrary element in {p1, p2, p3} and q an arbitrary vertex of G2.
`1. The subgraph generated by vertex p is exactly G2, and in addition we assumed that in ̅2 there is no
`1(cid:173)factor, so p is not T(cid:173)characterized.
`2. If we denote as Gq the subgraph generated by vertex q, then the set K of vertices of Gq are {p1, p2, p3}
`together with the neighbors of q in Gq. As each member of {p1, p2, p3} is a neighbor of every vertex in K,
` ̅p can be divided into two components, the vertex sets {p1, p2, p3} and K. The vertices {p1, p2, p3}
`together with the vertices in G comprise an odd number of vertices, thus it cannot contain a 1(cid:173)factor, and
`thus neither does ̅p. Hence q is clearly not T(cid:173)characterized, which proves the theorem.
`Using Theorems 9 and 11, we still only know an estimated value of nmin in the inequality in (25)
`in the case where k ≥ 6. The question is what the situation is when k = 2 and k = 4?

`In the k = 2 case, Γn,2 ∈ PR2 is exactly a Hamiltonian cycle, thus it is simple to see that for no
`value of n is Γn,2 a VP graph.

`
`Theorem 12. If k = 4 and n = k + 3, then Γ ∈PR is not a VP graph.
`
`
`
` OOF. We select Γ7,4 arbitrary p vertices and examine the subgraph of Γ7.4 generated by p, Gp. If p is
`not T(cid:173)characterized, then Gp contains the representation of the 1(cid:173)factors of the 4(cid:173)vertex complete graph
`constructed from the neighbors of p. As can be determined from figure 4, this is only possible in two
`cases: in either the a), d), f), g) case or the b), c), e), h) case.
`Using q1 and q2 we denote the points of Γ7.4 which are not in Gp and not identical to p (see figure
`15). In the first case Gp contains the first type of 1(cid:173)factor representation (see the bold line in figure 16).
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1017, p. 11 of 13
`
`

`
`Figure 15
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Figure 16
`
`
`
`
`
`
`
`
`
`
`
`
`
` [page 375]
`
`
`
`
`
`
`
`
`Because k = 4, vertex q1 (or q2) is a neighbor with at least two vertices from the representation, so for q2
`(or q1) at most three vertices remain as neighbors. That is, in this case, Γ7,4 cannot be constructed (see
`figure 17).
`In the second case Gp contains the second type of 1(cid:173)factor representation (shown in bold lines in
`figure 18).
`
`
`
`Figure 17
`
`
`
`
`
`
`
`Figure 18
`
`
`
`
`However then only one type of connecting of q1 and q2 remains (from the other vertices) for the Γ7,4
`construction (see figure 19), in which it is easy to find the T(cid:173)characterized vertex (these are indicated by
`―T‖ in figure 19).
We remark that using the graph construction from Theorem 10 with much more
`general assumptions can also give rise to a graph with the desired properties. However, our goal was only
`to demonstrate existence, for which this proves sufficient.
`Theorems 8, 10 and 11 enable to more exactly specify the inequality in (25) and we can give the
`following theorem:
`
`13. Theorem. For any even number k ≥ 4, the smallest n for which Γ ∈ PR is a VP graph is

`
`(26)
`
`nmin = k + 3 if k ≥ 6
`nmin = k + 4 if k = 4

`
`
`The k=4 case for Theorem 13 is depicted in figure 19 and figure 20 shows an example of the k=6 case.

`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1017, p. 12 of 13
`
`

`
`Figure 19
`
`
`
`
`
`
`
`
`
`
`
`Figure 20
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`[page 376]
`
`
`
`
`
`
`
`
`
`LITERATURE.
`
`[1] C. Berge: Graphs and hypergraphs. North(cid:173)Holland, 1973.

`
`[2] G. A. Dirac: Some theorems on abstract graphs. Proc. London Math. Soc. (3), 2 (1952), 69(cid:173)81.

`
` 3 . Erd s and . nyi: On the evolution of random graphs. Hungarian Academy of Sciences
`Mathematics Institute Proceedings, year V, series A, volumes 1(cid:173)2, 1960.
`
`[Title and author information appears in Russian.]
`[Title and author information appears in English.]
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`[page 377]
`
`
`
`
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1017, p. 13 of 13