I. Stephen Matthew Grimes, hereby certify that I transiated the attached document from
`
`Hungarian into English and that, to the best of my ability, it is a true and correct translation. I
`further certify that I am competent in both Hungarian and English to render and certify such
`translation.
`
`flfiitfluvrvv
`
`FULL LEGAL NAME
`
`Sworn to before me this ith day 0
`
`201.
`
`‘Z}_’1%fl/HA/l_C',€a.w¢u
`
`EXHIBIT
`
`(cid:44)(cid:51)(cid:53)(cid:21)(cid:19)(cid:20)(cid:25)(cid:16)(cid:19)(cid:19)(cid:26)(cid:21)(cid:25)(cid:16)(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:20)(cid:25)(cid:3)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:20)(cid:3)(cid:82)(cid:73)(cid:3)(cid:21)(cid:23)
`
`

`
`(cid:44)(cid:51)(cid:53)(cid:21)(cid:19)(cid:20)(cid:25)(cid:16)(cid:19)(cid:19)(cid:26)(cid:21)(cid:25)(cid:16)(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:20)(cid:25)(cid:3)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:21)(cid:3)(cid:82)(cid:73)(cid:3)(cid:21)(cid:23)
`
`from the University of Illinois at Urbana-Champaign Library
`Attachment 7a: Copy of Document 7
`
`

`
`(cid:44)(cid:51)(cid:53)(cid:21)(cid:19)(cid:20)(cid:25)(cid:16)(cid:19)(cid:19)(cid:26)(cid:21)(cid:25)(cid:16)(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:20)(cid:25)(cid:3)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:22)(cid:3)(cid:82)(cid:73)(cid:3)(cid:21)(cid:23)
`
`from the University of Illinois at Urbana-Champaign Library
`Attachment 7a: Copy of Document 7
`
`

`
`(cid:44)(cid:51)(cid:53)(cid:21)(cid:19)(cid:20)(cid:25)(cid:16)(cid:19)(cid:19)(cid:26)(cid:21)(cid:25)(cid:16)(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:20)(cid:25)(cid:3)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:23)(cid:3)(cid:82)(cid:73)(cid:3)(cid:21)(cid:23)
`
`from the University of Illinois at Urbana-Champaign Library
`Attachment 7a: Copy of Document 7
`
`

`
`(cid:44)(cid:51)(cid:53)(cid:21)(cid:19)(cid:20)(cid:25)(cid:16)(cid:19)(cid:19)(cid:26)(cid:21)(cid:25)(cid:16)(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:20)(cid:25)(cid:3)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:24)(cid:3)(cid:82)(cid:73)(cid:3)(cid:21)(cid:23)
`
`from the University of Illinois at Urbana-Champaign Library
`Attachment 7a: Copy of Document 7
`
`

`
`(cid:44)(cid:51)(cid:53)(cid:21)(cid:19)(cid:20)(cid:25)(cid:16)(cid:19)(cid:19)(cid:26)(cid:21)(cid:25)(cid:16)(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:20)(cid:25)(cid:3)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:25)(cid:3)(cid:82)(cid:73)(cid:3)(cid:21)(cid:23)
`
`from the University of Illinois at Urbana-Champaign Library
`Attachment 7a: Copy of Document 7
`
`

`
`(cid:44)(cid:51)(cid:53)(cid:21)(cid:19)(cid:20)(cid:25)(cid:16)(cid:19)(cid:19)(cid:26)(cid:21)(cid:25)(cid:16)(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:20)(cid:25)(cid:3)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:26)(cid:3)(cid:82)(cid:73)(cid:3)(cid:21)(cid:23)
`
`from the University of Illinois at Urbana-Champaign Library
`Attachment 7a: Copy of Document 7
`
`

`
`IPR2016-00726-
`ACTIVISION, EA,
`TAKE-TWO, 2K,
`ROCKSTAR, Ex.
`1016, p. 8 of 24
`
`from the University of Illinois at Urbana-Champaign Library
`Attachment 7a: Copy of Document 7
`
`

`
`(cid:44)(cid:51)(cid:53)(cid:21)(cid:19)(cid:20)(cid:25)(cid:16)(cid:19)(cid:19)(cid:26)(cid:21)(cid:25)(cid:16)(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:20)(cid:25)(cid:3)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:28)(cid:3)(cid:82)(cid:73)(cid:3)(cid:21)(cid:23)
`
`from the University of Illinois at Urbana-Champaign Library
`Attachment 7a: Copy of Document 7
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR,
`Ex.1016, p. 10 of 24
`
`from the University of Illinois at Urbana-Champaign Library
`Attachment 7a: Copy of Document 7
`
`

`
`[Back Cover]
`
`Price: 14 HUF [Hungarian Forints]
`Yearly subscription: 28 HUF
`
`Responsible Party for publication is Director of Academic Publishing
`Editorial content: István Sándor
`Date of publication: May 16, 1978 – Size: 17.85 (A/5) iv
`78-2482 – Szeged Press – Director: Jozsef Dobó
`
`Index: 25 564
`ISSN 0025—519X
`
`[Front Cover]
`
`Mathematical Proceedings
`János Bolyai Mathematical Society
`
`[Stamp: The Library of the University of Illinois]
`
`Edition 27: 1976-1979, 3-4
`
`(cid:44)(cid:51)(cid:53)(cid:21)(cid:19)(cid:20)(cid:25)(cid:16)(cid:19)(cid:19)(cid:26)(cid:21)(cid:25)(cid:16)(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:20)(cid:25)(cid:3)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:20)(cid:20)(cid:3)(cid:82)(cid:73)(cid:3)(cid:21)(cid:23)
`
`

`
`“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, (cid:299)n, the n-vertex complete graph, can be constructed from (cid:299)n-1, the complete graph
`on n-1 vertices, by adding a vertex and connecting it to each vertex of (cid:299)n-1. The same transformation on
`any other regular graph of other degree does not achieve the goal. Pal Érd(cid:280)s and Alfréd Ré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 (cid:299) = (P,E) be an n-vertex simple graph and pi (cid:1134)P, pj (cid:1134)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 (cid:299).)
`We take the EC transformation on vertex p to be the following:
`(1) EC: E (cid:314) E’(cid:850)
`where
` E’ = E \ {(pipj)} (cid:137) {(ppi), (ppj)}
`
`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 (cid:137) PR4 (cid:137) ... (cid:137) PRk (cid:137) ...
`
`2. (cid:1126)i (cid:122) j, (i, j even), PRi (cid:320) PRj =(cid:1486)
`
`3. (cid:1126)(cid:299)n,k (cid:1134)(cid:3)PRk, (cid:1129)! PRk: (cid:299)n,k (cid:1134)(cid:3)PRk ; that is, the set PR has a classification.
`
`Definition 2. Let (cid:299)n,k (cid:1134)(cid:3)PRk be an n-vertex, k-regular graph. Further suppose (cid:299)n,k = (P,E) and (cid:299)n+1 =
`
`(P (cid:137) {p}, E’), where p (cid:144) 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 (cid:299)n,k , then
`
`(2)
`
`ET: (cid:299)n,k (cid:314) (cid:299)n
`
`Mathematical Proceedings
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` [page 365]
`
`where E’ = E \ { (p1p2), (p3p4), ... , (pk-1pk) } (cid:137) { (pp1),(pp2), ... , (ppk) }
`
`Theorem 1. Let k be an even number. The ET transformation can be used for every (cid:299)n,k (cid:1134) PRk .
`
`PROOF. It is sufficient if we observe that in every (cid:299)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.”
`
`(cid:44)(cid:51)(cid:53)(cid:21)(cid:19)(cid:20)(cid:25)(cid:16)(cid:19)(cid:19)(cid:26)(cid:21)(cid:25)(cid:16)(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:20)(cid:25)(cid:3)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:20)(cid:21)(cid:3)(cid:82)(cid:73)(cid:3)(cid:21)(cid:23)
`
`

`
`If we take K to be a cycle of length k+1 in (cid:299)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
`
`neighbors of p but pairwise not neighbors. Then we take the ET transformation to be:
`
`(3) ET-1: (cid:299)n,k (cid:314) (cid:299)n-1 = (P’, E’), P’ = P \ {p}
`
`
`
` E’ = E \ { (pp1), (pp2), …, (ppk) (cid:137) { (p1p2),(p3p4), …,(pk-1pk) }
`
`Then we take the subgraph of (cid:299)n generated by p (designate this Gp = (P’, E’) ), and it turns out this is the
`
`Definition 3. Let (cid:299)n,k = (P,E) (cid:1488)(cid:3)PRk, p(cid:3)(cid:1488)(cid:3)P, and we take the vertex pairs p1p2, p3p4, ..., pk-1pk to be
`Definition 4. Let (cid:299)n,k = (P, E) be a graph on n vertices, p(cid:3)(cid:1488)(cid:3)P, and q1, q2, ... , qr be neighbors of p in (cid:299)n.
`subgraph where P’ = {q1, q2, ..., qr} and (qi, qj)(cid:1488) E(cid:397) (cid:1103) (qi, qj)(cid:1488) E .
`Definition 5. Let (cid:299)n(cid:1488) PR and p (cid:1488) (cid:299)n . Then the vertex p is T-characterized if the complement of the
`Theorem 2. The ET-1 transformation can be applied to a graph (cid:299)n,k = (P,K) (cid:1488)(cid:3)PRk if and only if there
`exists a T-characterized vertex p (cid:1488)(cid:3)(cid:299)n,k .
`
`subgraph on (cid:299)n generated by it contains a 1-factor.
`
`PROOF. Necessity: From the definition of ET-1 it follows that there exists p(cid:1134) (cid:299)n,k from which we can
`select neighbors p1p2, p3p4, ... , pk-1pk which are pairwise not neighbors. In the complement of the
`subgraph on (cid:299)n constructed on p1, p2, ... , pk they will be neighbors, and they comprise a 1-factor, as any
`two vertex pairs have no common vertex. This is precisely what it means for the vertex p to be
`T-characterized.(cid:850)
`
`Sufficiency: The proof in this direction is the exactly the reverse of the above necessity proof.
`
`Theorem 3. For every even k (cid:149) 4 there is a graph (cid:299)n,k(cid:1488)(cid:3)PRk which has no vertex p which is
`Equivalent formulation: For every even k (cid:149) 4 there exists a graph (cid:299)n,k(cid:1488) PRk for which no graph
`k+1,k = (P2, E2). Let (pi1, pj1)(cid:1488) E1 and (pi2, pj2)(cid:1488) E. Then we construct the following
`
`ROOF. Let k be an arbitrary even number, k (cid:149) 4. Let us examine two complete graphs on k+1 vertices
`(cid:299)1
`k+1,k = (P1, E2) and (cid:299)2
`
`T-characterized.
`
`(cid:299)n-1,k (cid:1134) PRk can be constructed with the ET transformation.
`
`(cid:3)P
`
`(cid:44)(cid:51)(cid:53)(cid:21)(cid:19)(cid:20)(cid:25)(cid:16)(cid:19)(cid:19)(cid:26)(cid:21)(cid:25)(cid:16)(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:20)(cid:25)(cid:3)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:20)(cid:22)(cid:3)(cid:82)(cid:73)(cid:3)(cid:21)(cid:23)
`
`

`
`graph (cid:299)n,k = (P , E)
`
`
`(4)
`(5)
`
`
`
`
`
`
`
`
`
`
`
`P = P1 (cid:137) P2
`E = E1 (cid:137) E2 \ { (pi1, pj1), (pi2, pj2) } (cid:137) { (pi1, pi2), (pj1, pj2) }}
`
`
`
`
`
`
`
`
`
` [page 366]
`
`The graph (cid:299)n,k where for k = 4 is illustrated in figure 2.
`
`(cid:3)
`
`Figure 2
`
`(cid:3)
`
`(cid:3)W
`
`e will demonstrate that (cid:299)n,k constructed in this way has does not have a T-characterized vertex.
`As every graph (cid:299)n,k constructed in this way is symmetric, for the proof it is enough to
`demonstrate for each vertex of the subgraph (for example (cid:299)1
`k+1,k). Here we can differentiate between two
`cases of selected pairs of vertices:
`
`a) pi1, pj1
`b) any other pair(cid:850)(cid:3)
`
`or the case in a), we take G1 = (A1, B1) to be the subgraph constructed on neighbors of p i1. Then:
`
`(cid:3)F
`
`(6)
`(7)
`
`(8)
`(9)
`
`A1 = P1 (cid:137) {pi2} \ {pi1}
`B1 = E1 \ { (pi2pr) | (cid:1126) pr (cid:1134) P1 \ {pi1} }
`
`A’1 = A1
`B’1 = E1 \ { (pi2ps) | (cid:1126)ps (cid:1134)(cid:3)P1 \{pi1} }
`
`So the complement (cid:10)(cid:3365)1 = (A’1, B’1) is therefore the following:
`So(cid:10)(cid:3365)1 does not contain a 1-factor, that is, p is not T-characterized (and similarly pi2, pj1, … , pj2). For the
`Then (cid:10)(cid:3365)2 = (A’, B’) will be the following:
`So(cid:10)(cid:3365)2 does not contain a 1-factor, that is, no vertex in case b) is T-characterized. And so the 2 theorem is
`
`case in b), let p (cid:1134)P1, p (cid:122) pi1 (cid:122) pj1, and G2 = (A2, B2) be the subgraph constructed on the neighbors of p:
`
`(10) A2 = P1 \ {p}
`(11) B2 = E2 \ { ( pi1pj1), (ppr) | (cid:1126) pr (cid:1134) P1 \ { p } }
`
`A’2 = A2
`(12)
`(13) B’2 = { ( pi1pj1 ) }
`
`proved.(cid:850)(cid:3)
`(cid:3)
`
`(cid:44)(cid:51)(cid:53)(cid:21)(cid:19)(cid:20)(cid:25)(cid:16)(cid:19)(cid:19)(cid:26)(cid:21)(cid:25)(cid:16)(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:20)(cid:25)(cid:3)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:20)(cid:23)(cid:3)(cid:82)(cid:73)(cid:3)(cid:21)(cid:23)
`
`

`
`In figure 3/a-d the graphs G1,(cid:10)(cid:3365)1, G2,(cid:3)(cid:10)(cid:3365)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-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-characterized. We take advantage of
`the following well-known result [1].
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` [page 367]
`
`Lemma 1. A complete graph (cid:299)n (where n is even) can be expanded into n-1 one-degree factors. (cid:850)
`
`(cid:3)T
`
`heorem 4. Let (cid:299)n,k (cid:1134)(cid:3)PRk and p (cid:1134) (cid:299)n,k = (P, E) . If p is not T-characterized, then there exist at least
`k-1 cycles of length 3 which contain p.
`
`PROOF. If p is not T-characterized, then the complement of the subgraph of (cid:299)n,k generated by it (G =
`
`least k-1. As it is the case in G that every edge endpoint is a neighbor of p, a 3-cycle containing p is thus
`constructed. And hence the theorem is proved.
`
`For k = 4, the following illustrations in figure 4/a-h depict cases where the vertex p is not T-characterized
`
`(A,B)) does not contain 1-factor. By Lemma 1, (cid:10)(cid:3365)(cid:3)(cid:133)ontains n-1 edge-independent 1-factors, and in G from
`these factors an edge must exist such that in (cid:10)(cid:3365) they are not a 1-factor. So the number of edges in G is at
`(bold edges indicate (cid:10)(cid:3365) ).
`(cid:4672)(cid:2924)(cid:2870)(cid:4673)(cid:4672)(cid:2924)(cid:2879)(cid:2870)(cid:2870) (cid:4673)(cid:485)(cid:4672)(cid:2870)(cid:2870)(cid:4673)
`(cid:4672)(cid:2924)(cid:2870)(cid:4673)(cid:488)
`
`Lemma 2. Let (cid:299)n be an n-vertex complete graph (n an even number) and we denote the number of all
`1-factors of (cid:299)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
`
`(cid:44)(cid:51)(cid:53)(cid:21)(cid:19)(cid:20)(cid:25)(cid:16)(cid:19)(cid:19)(cid:26)(cid:21)(cid:25)(cid:16)(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:20)(cid:25)(cid:3)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:20)(cid:24)(cid:3)(cid:82)(cid:73)(cid:3)(cid:21)(cid:23)
`
`

`
`k(cid:3409) n – 2, that is:
`(cid:4672)(cid:2921)(cid:2870)(cid:4673)(cid:4672)(cid:2921)(cid:2879)(cid:2870)(cid:2870) (cid:4673)(cid:485)(cid:4672)(cid:2870)(cid:2870)(cid:4673)
`(cid:4672)(cid:2921)(cid:2870)(cid:4673)(cid:488)
`
`Fk =
`
`(15)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` [page 368]
`
`Figure 4
`
`has two vertices beyond which k+1 new vertex pairs can be selected (we don’t take note of the
`Then (cid:299)
`k
`ordering of the two points), each of which has an F
` numbered 1-factor which each share exactly one
`edge, so
`
`k
`
`(16) F
`k+2
`
`= ( k + 1 ) (cid:194) F k
`
`Recalling that
`
`(cid:4672)(cid:2921)(cid:2878)(cid:2870)(cid:2870) (cid:4673)
`(cid:3169)(cid:3126)(cid:3118)(cid:3118)
`
`(17)
`
`So thus
`
`(18) Fk+2 =
`
` *
`
` =
`
`(cid:2870)(cid:1499)(cid:4666)(cid:2921)(cid:2878)(cid:2870)(cid:4667)(cid:488)
`(cid:2870)(cid:488)(cid:3)(cid:2921)(cid:488)(cid:4666)(cid:2921)(cid:2878)(cid:2870)(cid:4667) = k + 1
`(cid:4672)(cid:2921)(cid:2870)(cid:4673)(cid:4672)(cid:2921)(cid:2879)(cid:2870)(cid:2870) (cid:4673)(cid:485)(cid:4672)(cid:2870)(cid:2870)(cid:4673)
`(cid:4672)(cid:2921)(cid:2878)(cid:2870)(cid:2870) (cid:4673)
`(cid:3169)(cid:3118)(cid:488)
`(cid:3169)(cid:3126)(cid:3118)(cid:3118)
`
`(cid:4672)(cid:2921)(cid:2878)(cid:2870)(cid:2870) (cid:4673)(cid:4672)(cid:2921)(cid:2870)(cid:4673)(cid:485)(cid:4672)(cid:2870)(cid:2870)(cid:4673)
`(cid:3169)(cid:3126)(cid:3118)(cid:3118) (cid:488)
`
` =
`
`This concludes the proof of the theorem.(cid:850)(cid:3)
`
`orollary.
`
`(cid:3)C
`
`4.
`
`In the context of (16) we can write Fn recursively as follows:
`
`(19) Fn = (n - 1) (cid:194) Fn-2(cid:850)(cid:3)
`
`2. The proof of Lemma 2 shows that if e is an edge contained in an E 1-factor of (cid:299)n, then exactly Fn-2 such
`
`(cid:44)(cid:51)(cid:53)(cid:21)(cid:19)(cid:20)(cid:25)(cid:16)(cid:19)(cid:19)(cid:26)(cid:21)(cid:25)(cid:16)(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:20)(cid:25)(cid:3)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:20)(cid:25)(cid:3)(cid:82)(cid:73)(cid:3)(cid:21)(cid:23)
`
`

`
`1-factors are in (cid:299)n which with E contain exactly the ei shared edges.
`
`3.If the number of distinct 1-factors in (cid:299)n is denoted FDn, then based on Lemma 1 and (19) we have:
`
`FDn = Fn (cid:1103)(cid:3)n-1 = (n-1) (cid:194)Fn-2 (cid:1101)(cid:3)1=Fn-2 (cid:1101)(cid:3) n=4
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` [page 369]
`
`4. The correspondence to (14) can be simplified by hiding the numerator as follows:
`
` = (cid:2924)(cid:488)(cid:2870)(cid:3172)(cid:512)(cid:3118)(cid:3)(cid:3172)(cid:3118)(cid:488)
`(cid:3118)(cid:488)(cid:4666)(cid:3172)(cid:3127)(cid:3118)(cid:4667)(cid:488)(cid:3)(cid:4666)(cid:3172)(cid:3127)(cid:3118)(cid:4667)(cid:488)
`(cid:3118)(cid:488)(cid:4666)(cid:3172)(cid:3127)(cid:3120)(cid:4667)(cid:488)(cid:485)(cid:3118)(cid:488)(cid:3118)(cid:488)(cid:3116)(cid:488)
`(cid:3172)(cid:488)
`(cid:3172)(cid:3118)(cid:488)
`
`
`
`Fn =
`
`Definition 7. Let (cid:299)n be a graph with n vertices and let
`
`(20)
`
`E = { E1, E2, … , Em }
`
`be a set of 1-factors of (cid:299)n and e1, e2 , …, ep be edges of (cid:299)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 (cid:299)n be a complete graph (n even). Denote the set of all 1-factors of (cid:299)n as
`
`(21) E = { E1, E2, ... , Er} where r = Fn and (cid:850)
`
`Ek(cid:1488)E for which ei(cid:1488)E and ej(cid:1488)E .
`PROOF. Necessity: Suppose that R is a representation of E and there exist ei (cid:122) ej and Ek where ei(cid:1488) Ek and
`
`ej (cid:1134) Ek . On the basis of Lemma 2, Corollary 2, ei represents an Fn-2 1-factor of E, and ej does also. As
`both edges are in Ek, it is the case that the for the 1-factor Kij represented by the two edges, it holds that(cid:850)(cid:3)
`
`(23) Kij < 2 (cid:194) Fn-2(cid:3)
`
`(cid:3)I
`
`f we suppose that the remaining n-3 edges in R represent the maximum n-1 1-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) (cid:194) Fn-2
`
`which is a contradiction, as the number of elements in E is (n - 1) (cid:194) Fn-2 and R is a representation
`of E, so for KE the equality must hold.
`
`Sufficiency: As every Ek(cid:1488)(cid:3)E 1-factor contains only one edge ei(cid:1488)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 R numbering (n - 1) (cid:194) Fn-2,
`this is all of the edges of E.
`We have proved the theorem.
`
`(cid:3)
`
`(cid:44)(cid:51)(cid:53)(cid:21)(cid:19)(cid:20)(cid:25)(cid:16)(cid:19)(cid:19)(cid:26)(cid:21)(cid:25)(cid:16)(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:20)(cid:25)(cid:3)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:20)(cid:26)(cid:3)(cid:82)(cid:73)(cid:3)(cid:21)(cid:23)
`
`(22) R = { e1, e2 , …, en-1} (cid:850)
`
`a set of edges of (cid:299)n. Then R is a representation of E if and only if for any two ei (cid:122) ej , there does not exist
`
`

`
`Theorem 5. For a complete graph (cid:299)n (n > 4, even), all 1-factors can be represented by exactly n-1 edges if
`and only if those edges are joined by a vertex.
`
`PROOF. Necessity: Let p (cid:1134) (cid:299)n be such a vertex. As every 1-factor of (cid:299)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 (cid:299)n .
`
`Sufficiency: Let us examine an arbitrary edge (p1p2) (cid:1134) (cid:299)n (p1 and p2 are the endpoints of edge ei). Let this
`be the first element of the n-1 element representation. By Lemma 3, the second element can only be
`selected from amongst such ej for which the only 1-factor containing ei does not also appear.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` [page 370]
`
`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,
`
`
`
` 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-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 (cid:299)n,k(cid:1488) 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-composition of graphs Ci1, Ci2, ... , Cit (indicated by “t”) is a graph (cid:299) = (P , E) where
`the following are true:
`
`(b)(cid:3)
`
`(a)
`
`(c)
`
`P = P1(cid:1515) P2(cid:1515) ...(cid:1515)(cid:3) Pt , (cid:1126)i (cid:122) j: Pi (cid:136) Pj = (cid:1486)
`E = E1(cid:1515) E2(cid:1515)...(cid:1515) Et(cid:1515) E’, (cid:1126)I (cid:122) j: Ei (cid:136) Ej = (cid:1486) where E’ is the set of so-called connector edges.
`
`(cid:299) is a regular graph
`
`(cid:44)(cid:51)(cid:53)(cid:21)(cid:19)(cid:20)(cid:25)(cid:16)(cid:19)(cid:19)(cid:26)(cid:21)(cid:25)(cid:16)(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:20)(cid:25)(cid:3)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:20)(cid:27)(cid:3)(cid:82)(cid:73)(cid:3)(cid:21)(cid:23)
`
`

`
`COMMENTS.
`1. The set E’ of edges is not easily determined.
`
`graph from complete subgraphs and i1 = i2 = .... = it.
`3. If (cid:299) = (cid:299)n,k and max(i1, i2, ..., it ) = L, then L (cid:148) k+1.(cid:850)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` [page 371]
`
`if n odd or
`
`vertex which has no pair in P \ P’, that is, (cid:299)n does not contain a 1-factor.
`
`2. E’ determines the connectedness of the graph (cid:299). That is, if E’ = (cid:1486), then (cid:299) is a t-component regular
`Theorem 6. Let (cid:299)n = (P, E) be a connected graph on n vertices. If in (cid:542)(cid:3364)n there exists a complete subgraph
`on [(cid:2924)(cid:2870)]+ 1 vertices, then in (cid:299)n there is no 1-factor. (We will use (cid:542)(cid:3364)n to indicate the graph complement of (cid:299)n.)
`PROOF. Let G = (P’, E’) be an [(cid:2924)(cid:2870)] + 1 vertex complete subgraph. Then
`|P(cid:397)| = [(cid:2924)(cid:2870)] + 1 (cid:1101) |P (cid:1148)(cid:3)P(cid:397)| = [(cid:2924)(cid:2870)]
` = [(cid:2924)(cid:2870)]-1 if n even.
`In (cid:542)(cid:3364)n the vertices of P’ can only be connected to vertices of P \ P’, so certainly in P’ there is at least one
`Theorem 7. Let (cid:299)n,k(cid:1488)(cid:3)PR and k (cid:149) 4. Further suppose the following:
`1. Cij(cid:1488)(cid:3)C , j=1,2,...,t (cid:149)2.
`3. (cid:2921)(cid:2878)(cid:2872)(cid:2870) (cid:148) ij (cid:148) k j =1,2,...,t (cid:149) 2
`conditions for Theorem 6 because (cid:2921)(cid:2878)(cid:2872)(cid:2870) (cid:148) i (cid:148) k. That is, the complement of the subgraph generated by p
`
`2. (cid:299)n,k is the t-composition of Ci1, Ci2, ..., Cit
`
`Then (cid:299)n,k is a VP graph.
`
`PROOF. We shall examine an arbitrary vertex p in (cid:299)n,k . Then from property b) of the t-composition, it
`follows that there exists Cij in (cid:299) where p (cid:1134) Cij and ij fulfills the conditions of Theorem 3. If we now
`examine the subgraph of (cid:299)n,k generated by p, there are k vertices and it contains Cij, which fulfills the
`
`does not contain a 1-factor. This means that p is not T-characterized. As we did not connect an edge to p,
`it can be done to any vertex in (cid:299)n,k , so (cid:299)n,k is a VP graph.
`
`A graph meeting conditions 1, 2, and 3 is shown in Figure 7.
`
`Figure 7
`
`(cid:44)(cid:51)(cid:53)(cid:21)(cid:19)(cid:20)(cid:25)(cid:16)(cid:19)(cid:19)(cid:26)(cid:21)(cid:25)(cid:16)(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:20)(cid:25)(cid:3)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:20)(cid:28)(cid:3)(cid:82)(cid:73)(cid:3)(cid:21)(cid:23)
`
`

`
`COMMENTS.(cid:850)(cid:3)
`1. From the proof of Theorem 7 it easily follows that to the extent that in (cid:299)n,k there are
`
`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
`
`subgraphs Cij (cid:1134) C, where ij = (cid:2921)(cid:2870) + 1, then (cid:299) is not a VP graph. Such a graph is shown in figure 8.
`and i1 = i2 = .(cid:2921)(cid:2878)(cid:2872)(cid:2870) , and we get that the number of vertices is n = k + 4 for the t-composition of Ci1 and Ci2
`
`= (cid:299)n,k VP graph.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` [page 372]
`
`From this follows the following theorem: (cid:850)
`
`(cid:3)
`
`Figure 8
`
`(cid:3)
`
`heorem 8. For any even number k (cid:149) 4 there exists a (cid:299)n,k VP graph where n = k + 4.
`
`(cid:3)T
`
`1 and (cid:299)k+1.k is complete there is no VP graph, so the question arises, for the given k cases, what is the
`
`As an example, in figure 9 we can see a (cid:299)8,4 graph. As we know, for any (cid:299)n,k(cid:1488) PR where n (cid:149) k +
`smallest nmin number for which there exists (cid:299)n,k(cid:1488) PR a VP graph.
`9.Theorem. If (cid:299) (cid:1488)(cid:3)PR and n = k+2, then (cid:299) is not a VP graph.
`
`Taking into account Theorem 8, it follows that
`
`(25)
`
`k+2 (cid:148) mmin (cid:148) k + 4
`
`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.
`
`(cid:3)
`
`(cid:44)(cid:51)(cid:53)(cid:21)(cid:19)(cid:20)(cid:25)(cid:16)(cid:19)(cid:19)(cid:26)(cid:21)(cid:25)(cid:16)(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid