Graph theory question

[James A. Donald]

In order to solve a sybil problem, want to show that each peer is 
accepted as a peer by three peers, and we don't want these peers to be 
sybils.

Related directed graph problem: Google trying to distinguish real links 
from networks of fake websites giving links to each other.

Suppose you have an undirected graph in which every vertex is connected 
to at least three other vertexes (because we collapse vertices with only 
one connection or two connections)

Now suppose we want to make sure that the total graph is well connected 
- that every subgraph is connected to at least three vertexes of the 
rest of the graph.  We want to collapse subgraphs that are only 
connected to the rest of the graph by one connection into the vertex by 
which they are connected, and collapse subgraphs that are only connected 
to rest of the graph by two connections into a single edge.

And suppose our graph is very large, thousands, perhaps millions, of 
vertices

Purported peers that have only one connection are clients of the entity 
to which they are connected, and he is responsible for their good 
behavior, similarly those that have only two connections.  Three good 
peer connections make you a peer of all the other peers, two good 
connections do not make you a peer - don't get equal treatment to the 
vertices by which you are connected, get graylist treatment.


---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus