Discrete mathematics for gate- Relation b/w Vertices and Edges in Simple graph

Discrete mathematics for gate- Relation b/w Vertices and Edges in Simple graph

Discrete Mathematics for GATE – Relationship Between Vertices and Edges in a Simple Graph

In graph theory, a simple graph is an unweighted, undirected graph that does not contain multiple edges or self-loops. The relationship between vertices (V) and edges (E) in a simple graph follows several important properties and theorems.

1. Basic Terminology

• Graph (G): A pair $G=(V,E)$ where:

  • $V$ is a finite set of vertices (nodes).
  • $E$ is a set of edges (connections between vertices).

• Simple Graph: A graph with no self-loops and no multiple edges.

• Degree of a Vertex ($deg(v)$): The number of edges connected to vertex $v$.

• Maximum edges in a Simple Graph: If a simple graph has $n$ vertices, the maximum number of edges is:

  Emax=n(n−1)2E_{max} = \frac{n(n-1)}{2}Emax​=2n(n−1)​

  (This occurs when the graph is complete, i.e., every pair of vertices is connected.)

2. Handshaking Theorem

For any undirected graph, the sum of the degrees of all vertices is twice the number of edges:

∑v∈Vdeg(v)=2∣E∣\sum_{v \in V} deg(v) = 2|E|v∈V∑​deg(v)=2∣E∣

Example:
Consider a graph with 4 vertices and the following degrees:
deg(v1)=2deg(v_1) = 2deg(v1​)=2, deg(v2)=3deg(v_2) = 3deg(v2​)=3, deg(v3)=3deg(v_3) = 3deg(v3​)=3, deg(v4)=2deg(v_4) = 2deg(v4​)=2.
Then,

$$2+3+3+2=10=2\times 5$$

So, the graph has 5 edges.

3. Bounds on Number of Edges

1. Minimum Edges: A graph with $n$ vertices can have as few as 0 edges (if it’s an edgeless or null graph).
2. Maximum Edges in a Simple Graph (Complete Graph):
   • A complete graph KnK_nKn​ has every vertex connected to every other vertex.
   • The number of edges in a complete graph is: ∣E∣=n(n−1)2|E| = \frac{n(n-1)}{2}∣E∣=2n(n−1)

4. Relationship Between Vertices and Edges in Special Graphs

5. Important GATE Questions

Q1: What is the maximum number of edges in a simple graph with 6 vertices?
Solution:

Emax=6(6−1)2=6×52=15E_{max} = \frac{6(6-1)}{2} = \frac{6 \times 5}{2} = 15Emax​=26(6−1)​=26×5​=15

So, the maximum edges = 15.

Q2: A simple graph has 7 vertices, and the sum of all vertex degrees is 18. Find the number of edges.
Solution (Handshaking Theorem):

$$\sum deg(v)=2|E|$$ $$18=2|E|\Rightarrow |E|=9$$

So, the graph has 9 edges.

6. Conclusion

 A simple graph follows basic properties like the handshaking theorem.
 The maximum number of edges in a simple graph is n(n−1)2\frac{n(n-1)}{2}2n(n−1)​.
 These properties help in solving GATE problems related to graph theory.

 Need more GATE-level problems on this topic? Let me know!

Discrete mathematics for gate- Relation b/w Vertices and Edges in Simple graph

GRAPH THEORY WITH APPLICATIONS