Application of the Handshaking Lemma in the Dyeing Theory of Graph

Article Information

Roland Forson*1, Cai Guanghui1, Richmond Nii Okle1, Daniel Ofori Kusi2, Elise Hamunyela3

1Department of Statistics and Mathematics, Zhejiang Gongshang University

2Department of Mathematics, University of Free State, South Africa

3Department of Mathematics, University of Namibia

*Corresponding Author: Roland Forson, Department of Statistics and Mathematics, Zhejiang Gongshang University, China

Received: 01 December 2019; Accepted: 10 December 2019; Published: 30 December 2019

Citation: Roland Forson, Cai Guanghui, Richmond Nii Okle, Daniel Ofori Kusi, Elise Hamunyela. Application of the Handshaking Lemma in the Dyeing Theory of Graph. Journal of Analytical Techniques and Research 1 (2019): 064-067.

Share at Facebook


The handshaking lemma is one of the important branches of graph theory. The content is widely applied in topology and computer science. The basis of the development of the dyeing theory used in this research paper is to discuss the application of the right transfer method in dyeing theory.


Right transfer method; Four-color conjecture; Dyeing graph theory; Euler; Handshaking lemma

Right transfer method articles, Four-color conjecture articles, Dyeing graph theory articles, Euler articles, Handshaking lemma articles

Statistics articles Statistics Research articles Statistics review articles Statistics PubMed articles Statistics PubMed Central articles Statistics 2023 articles Statistics 2024 articles Statistics Scopus articles Statistics impact factor journals Statistics Scopus journals Statistics PubMed journals Statistics medical journals Statistics free journals Statistics best journals Statistics top journals Statistics free medical journals Statistics famous journals Statistics Google Scholar indexed journals graph theory articles graph theory Research articles graph theory review articles graph theory PubMed articles graph theory PubMed Central articles graph theory 2023 articles graph theory 2024 articles graph theory Scopus articles graph theory impact factor journals graph theory Scopus journals graph theory PubMed journals graph theory medical journals graph theory free journals graph theory best journals graph theory top journals graph theory free medical journals graph theory famous journals graph theory Google Scholar indexed journals Right transfer method articles Right transfer method Research articles Right transfer method review articles Right transfer method PubMed articles Right transfer method PubMed Central articles Right transfer method 2023 articles Right transfer method 2024 articles Right transfer method Scopus articles Right transfer method impact factor journals Right transfer method Scopus journals Right transfer method PubMed journals Right transfer method medical journals Right transfer method free journals Right transfer method best journals Right transfer method top journals Right transfer method free medical journals Right transfer method famous journals Right transfer method Google Scholar indexed journals Four-color conjecture articles Four-color conjecture Research articles Four-color conjecture review articles Four-color conjecture PubMed articles Four-color conjecture PubMed Central articles Four-color conjecture 2023 articles Four-color conjecture 2024 articles Four-color conjecture Scopus articles Four-color conjecture impact factor journals Four-color conjecture Scopus journals Four-color conjecture PubMed journals Four-color conjecture medical journals Four-color conjecture free journals Four-color conjecture best journals Four-color conjecture top journals Four-color conjecture free medical journals Four-color conjecture famous journals Four-color conjecture Google Scholar indexed journals Dyeing graph theory articles Dyeing graph theory Research articles Dyeing graph theory review articles Dyeing graph theory PubMed articles Dyeing graph theory PubMed Central articles Dyeing graph theory 2023 articles Dyeing graph theory 2024 articles Dyeing graph theory Scopus articles Dyeing graph theory impact factor journals Dyeing graph theory Scopus journals Dyeing graph theory PubMed journals Dyeing graph theory medical journals Dyeing graph theory free journals Dyeing graph theory best journals Dyeing graph theory top journals Dyeing graph theory free medical journals Dyeing graph theory famous journals Dyeing graph theory Google Scholar indexed journals Euler articles Euler Research articles Euler review articles Euler PubMed articles Euler PubMed Central articles Euler 2023 articles Euler 2024 articles Euler Scopus articles Euler impact factor journals Euler Scopus journals Euler PubMed journals Euler medical journals Euler free journals Euler best journals Euler top journals Euler free medical journals Euler famous journals Euler Google Scholar indexed journals Handshaking lemma articles Handshaking lemma Research articles Handshaking lemma review articles Handshaking lemma PubMed articles Handshaking lemma PubMed Central articles Handshaking lemma 2023 articles Handshaking lemma 2024 articles Handshaking lemma Scopus articles Handshaking lemma impact factor journals Handshaking lemma Scopus journals Handshaking lemma PubMed journals Handshaking lemma medical journals Handshaking lemma free journals Handshaking lemma best journals Handshaking lemma top journals Handshaking lemma free medical journals Handshaking lemma famous journals Handshaking lemma Google Scholar indexed journals topology articles topology Research articles topology review articles topology PubMed articles topology PubMed Central articles topology 2023 articles topology 2024 articles topology Scopus articles topology impact factor journals topology Scopus journals topology PubMed journals topology medical journals topology free journals topology best journals topology top journals topology free medical journals topology famous journals topology Google Scholar indexed journals computer science articles computer science Research articles computer science review articles computer science PubMed articles computer science PubMed Central articles computer science 2023 articles computer science 2024 articles computer science Scopus articles computer science impact factor journals computer science Scopus journals computer science PubMed journals computer science medical journals computer science free journals computer science best journals computer science top journals computer science free medical journals computer science famous journals computer science Google Scholar indexed journals maximum edge method articles maximum edge method Research articles maximum edge method review articles maximum edge method PubMed articles maximum edge method PubMed Central articles maximum edge method 2023 articles maximum edge method 2024 articles maximum edge method Scopus articles maximum edge method impact factor journals maximum edge method Scopus journals maximum edge method PubMed journals maximum edge method medical journals maximum edge method free journals maximum edge method best journals maximum edge method top journals maximum edge method free medical journals maximum edge method famous journals maximum edge method Google Scholar indexed journals

Article Details

1. Introduction

The four-color problem forms the famous four-color conjecture. The four-color conjecture is available for any flat-picture graph   such that, . The four-color lemma has seen extensive research in graph theory, but the problem is NP-hard and computer results proved convincing in edge-dyed [2], surface-dyed [3, 4] , and color-dyed [1, 8]  with a restricted strip. In the literature above, the methods of proof commonly used in mathematics, such as the traditional direct proof method, the reverse proof method, the mathematical induction method, etc., and the graph theory proves its unique method and technology, such as the shortest (long) path method, and the maximum edge method [1, 5, 8].

2. The Development of Dyeing Theory

The process of applying the weight transfer method is based on the handshake lemma. Let G be a connected plane graph, then according to Euler theorem;

Where is the number of vertices of G, the number of edges of G is ε, and the number of planes of G is ?. The handshake lemma [2, 5, 9]  sets G as a communication flat graph, and that, Where F(G)is the face set of G.

If we set G as a connected flat chart, for any real number k,l>0; following constant equation is established:

3. Power Transfer Method

Applying Euler Formula and handshaking lemma,

explains the sum of the initial rights as a constant. By using the nonexistence of reducible sub-graphs, it is shown that the total number of new weight sums is different from the total number of initial weight sums [2, 10], and thus obtains the contradiction. It is proven that such a minimal counterexample of G does not exist [12, 13], so the graph belonging to C has the P attribute.

For any, We remember denotes the weight transferred from x to y. To begin with, every element in , the graph G remains unchanged; the new weight of each element is not negative, which contradicts the Euler formula. In practice, this is often the case: Yes, arbitrary

defines graph G as follows:

This follows that,

. The weights of each element are adjusted to . Since it is only transferred within the elements, the addition and retention of the graph remains the same, that is, Furthermore we define an appropriate weight transfer rule, and verify that each conforms to a certain rule structure, such as the result obtained which is a contradiction, and the conclusion is proved.

Below 4 cases:

We give an example to illustrate the application of weight transfer method [7, 9]. Let G be a simple plan, and if , Then one of the following conditions holds:

(I) G contains a 2-point adjacent to a 2-point;

(II) G contains a 3-point adjacent to a 2-point and a ≤ 3-point;

(III) G contains a d-point adjacent to (d -1) 2-points, where d ≥ 4


It is proved that G is the least reverse example to meet the example condition, and the Euler defined formula can be rewritten into the following form;

 Then, defines the initial weight function

provided that The transfer of power method is then used to obtain a new number of ω', where the rules for transfer of power are as follows:

(R1): Transfer from each ≥3 point to each of its adjacent 2-points is 2

(R2); Transfer from each ≥4 point to each of its adjacent vertex v, if d(v)=2, then there is a transfer 2 to d(v)=3, from1

we proved that, , and that is a contradiction.

The set F(G) is such that, . Set v is any vertex of Figure G, if d(v)=2 the

such that, d(v)=3 is attached to the Nv(G). Thus all the

and that

and that

Thus, as proved.


  1. West DB. Introduction to graph theory. Upper Saddle River, NJ: Prentice hall 2 (1996). 
  2. Gross JL, Yellen J (Eds.). Handbook of graph theory. CRC press (2004).
  3. Bondy JA, Murty USR. Graph theory with applications. London: Macmillan 290 (1976). 
  4. Godsil C, Royle GF. Algebraic graph theory. Springer Science and Business Media 207 (2013). 
  5. Bollobás B. Modern graph theory. Springer Science and Business Media 184 (2013). 
  6. Biggs N, Biggs NL, Norman B. Algebraic graph theory. Cambridge university press 67 (1993). 
  7. Golumbic MC. Algorithmic graph theory and perfect graphs. Elsevier 57 (2004). 
  8. Forson R. Hamiltonicity of Total Domination 3-Connected Edge Critical Graph. Available at SSRN 2941978 (2017).
  9. Gross JL, Tucker TW. Topological graph theory. Courier Corporation (2001). 
  10. Forson R, Guanghui C, Ofori S, et al. The Distribution Properties of Two-Parameter Exponential Distribution Order Statistics.
  11. Gibbons A. Algorithmic graph theory. Cambridge university press (1985).
  12. Golumbic MC. Algorithmic graph theory and perfect graphs. Elsevier 57 (2004).
  13. Forson R, Nweit OT. A Generalization of Probabilistic Cauchy-Schwarz Inequality. Available at  SSRN3080064 (2017).

© 2016-2024, Copyrights Fortune Journals. All Rights Reserved