note1.adoc

Graph Theory with Applications to Engineering & Computer Science (Narsingh Deo)

If v_i is connected to e_j, the vertex is said to be incident to the edge, and vice-versa.

A (degree|valency) is the number of edges connected to a particualr vertex, this includes self-connecting edges.

• Theorem 0: The sum of the degress of all vertices, will always be twice the amount of edges

Proof:

\(\sum_{i=1}^n d(v_{i}) = 2E\)

We know that for each edge there are exactly two vertices, which connect to each other. Contributing 2 to the total sum of degree.

\(E = \frac{\sum_{i=1}^n d(v_{i})}{2}\)

or, conversely

\(2E = \sum_{i=1}^n d(v_{i})\)

• A Regular Graphs is a graph where the degree of each vertex is equal \(degree(v_{i}) = d\)

• A Null Graph is a graph with no edges, eg all vertices have the degree 0

Note	a graph must contain atleast one vertex to be a graph at all.

Note	the 4-color-problem is a popular conjecture in CS, specifically graph theory. It states that a map, can be filled with atleast 4 distinct colors without same adjacent colors.

A graph is called isomorphic (equivalent to congruence in geomtry) if the incidence between the edges ands vertices is maintained. That is, if e_i is incident to v₁, v₂ then 'e_i ⇒ 'v₁, 'v₂. Two graphs are isomorphic, if they share the same number of vertices and edges, the same degree across the vertices and a bijection between the adjacencies acorss different vertices.

graph g is said to be a subgraph of G if for vertex i \(g(v_{i}) \in G\) and every vertex g is also in G that is \(G(v_{i}) = g(v_{j})\) and every edge of graph g also connects within graph G

Theorem 2.0 A graph is disconnected if and only if its vertex set V can be partioned into two or more sets such that no edge has either of it’s endpoints in different subsets.

Proof For a graph to be considered connected there needs to be a path between each vertex pair in the graph, according to the statement the graph is partionined into two subsets, such that there isn’t an edge that connects any vertex in subset A or B we can say the graph is disconnected. Conversely if we have a disconnected graph, and we pick a vertex A and form a subset that contains all paths from A to every other vertex, the remaining vertices will form a disjointed subset.

Theorem 2.1 If a graph has just two vertices, of an odd degree there must be at-least one path joining them

Proof Since we are provided with two vertices, an even degree on either of them would imply a self-loop since there isn’t any other node to connect with, hence an odd degree is would guarantee that the two vertices are connected