# Graph theory question

```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

```