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

In Discrete Mathematics, especially in the context of GATE CSE, understanding the relationship between vertices and edges in a simple graph is essential. Let’s break it down:

Definition: Simple Graph

A simple graph is an undirected graph that:

• Has no self-loops (an edge connecting a vertex to itself)

• Has no multiple edges (no two edges connect the same pair of vertices)

Basic Properties – Vertices (V) and Edges (E)

Let:

• $V$ be the number of vertices

• $E$ be the number of edges

1. Maximum Number of Edges in a Simple Graph

For a simple undirected graph with $n$ vertices:

Maximum number of edges,Emax=n(n−1)2\text{Maximum number of edges}, E_{\text{max}} = \frac{n(n-1)}{2}Maximum number of edges,Emax​=2n(n−1)​

This is because each pair of distinct vertices can have at most one edge.

2. Sum of Degrees of All Vertices

The degree of a vertex is the number of edges incident on it.

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

This is known as the Handshaking Theorem.

3. Minimum and Maximum Edges

• Minimum edges in a simple graph:

  • 0, when there are no connections (empty graph)

• Maximum edges (as above):

  • n(n−1)2\frac{n(n-1)}{2}2n(n−1)​

Example:

Let’s say we have a simple graph with $n=4$ vertices.

• Max possible edges:

  Emax=4(4−1)2=122=6E_{\text{max}} = \frac{4(4 – 1)}{2} = \frac{12}{2} = 6Emax​=24(4−1)​=212​=6

• Suppose we have a graph with 3 edges:

  • Total degree = $2\times 3=6$

  • So, degrees of all vertices might be: 2, 2, 1, 1

Application in GATE Questions

You may be asked:

• Find the max/min number of edges for a given number of vertices

• Use Handshaking theorem to find missing degrees

• Identify number of vertices given number of edges and degree pattern

Key Concepts to Revise:

• Types of graphs (simple, multigraph, complete, etc.)

• Handshaking Lemma

• Complete Graphs KnK_nKn​

• Bipartite Graphs and their edge bounds

Would you like a diagram or GATE-style question on this topic?

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

Mathematics (Discrete Structure).pdf