[go: up one dir, main page]
Scribd
Upload
70 views2 pages

Assignment Number 1

1) Every simple graph with n vertices is a subgraph of the complete graph Kn. This is because every vertex in the simple graph G is also a vertex in the complete graph Kn, so G must be a subgraph of Kn. 2) If a k-regular bipartite graph has bipartition (X,Y) where k>0, then the sets X and Y must be the same size. This is because each vertex must have degree k, so there cannot be more vertices in one part than the other. 3) The edge graph of a graph G has the edges of G as its vertices. Two vertices in the edge graph are adjacent if their corresponding edges in G are adjacent. The

Uploaded by

Qaiser Muhammad
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
70 views2 pages

Assignment Number 1

1) Every simple graph with n vertices is a subgraph of the complete graph Kn. This is because every vertex in the simple graph G is also a vertex in the complete graph Kn, so G must be a subgraph of Kn. 2) If a k-regular bipartite graph has bipartition (X,Y) where k>0, then the sets X and Y must be the same size. This is because each vertex must have degree k, so there cannot be more vertices in one part than the other. 3) The edge graph of a graph G has the edges of G as its vertices. Two vertices in the edge graph are adjacent if their corresponding edges in G are adjacent. The

Uploaded by

Qaiser Muhammad
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Graph Theory (First Assignment)

Submitted by: Qaiser Muhammad Abdur Rehman


Student No: 11917024
1.4.1: Every simple diagram of n vertices is isomorphic in a subgraph of Kn.
Proof: Set G is any simple graph with n vertices, and Kn's vertices are n, And Kn
is a complete diagram, by the definition of G is a subplot of Kn. by G's
arbitrariness, Propositions can be proved.

1.5.3: If a k-regular bipartite graph with k > 0 has bipartition (X, Y), then |x| =
|Y|.
Proof: Take k regular even graph G (V, E), defined by the even graph and
handshake theorem, then The two endpoints of e . . . are in X and Y,
respectively.
Suppose the s.X. sm, smh.com.au s n, sg. ≥ m and n (m, n are positive integers),
so there must be a little v0 in Y, so that d (v0) and d (v) are k, and G is the
contradiction of k regular.
The same, take the g. There is also the presence of v0', so that d (v0') is k. so m is
n, i.e. |x| = |Y|.

1.5.10: The edge graph of a graph G is the graph with vertex set E(G) in which
two vertices are joined if and only if they are adjacent edges in G. Show that, if
G is simple

(a) the edge graph of G has ε(G) vertices and ∑ (𝑑𝐺(𝑣)


2
) edges;
𝑣∈𝑉(𝐺)
(b) the edge graph of K5 is isomorphic to the complement of the graph featured
in exercise 1.2.6.

Proof: (a) First, as can be seen by the definition of the edge graph, G's edge
chart H contains all of G's Vertex, so the number of vertices in its edge chart is
equal to g.
G is a simple graph, and its edge chart H is also it The subplot.
By the handshake theorem, the number of edges of H is equal to the degree and
half of its vertex, That is, ∑ (𝑑𝐺(𝑣)
2
)
𝑣∈𝑉(𝐺)

You might also like