Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

0
votes
1answer
18 views

quotient graph $G^R$

I understand that if $R$ is an equivalence relation on $G$, the resulting partition cells are either equal or disjoint. I think I understand that the graph of the quotient set $G^R$ is constructed ...
0
votes
1answer
38 views

Proving a connected graph cannot have only even-degree vertices

I want to prove that a connected graph with m edges and n vertices must have at least one vertex of odd degree. In particular, I want to prove this for a graph of 53 edges and 11 vertices; but also in ...
0
votes
1answer
34 views

How to justify the statement that a graph is connected?

Is the graph connected? Justify. Because there is a path connecting all pairs of vertices, this graph is therefore connected? Is that right?
0
votes
1answer
39 views

What is meant by “connected components” in a graph?

I read the following statement : If the graphs $G$ and $G'$ are isomorphic then following is true: If $G$ is connected, so is $G'$. More generally, $G$ and $G' $ have same number of ...
0
votes
2answers
12 views

Degree of a vertex in following graph.

If I have the following graph : Should the degree of vertex $v_2$ be 1 or 2...I'm asking this because I'm not sure whether loop should be counted while considering degree... (In my notes the ...
0
votes
1answer
24 views

Is the number of simple circuits of a particular length preserved in two isomorphic graphs?

If two graphs are isomorphic, and one has a simple circuit of a particular length, must the other graph also have a circuit of the same length? Do they also have to have the same number of such ...
0
votes
1answer
20 views

Orientation digraph question

Let $G$ be nontrivial connected graph without bridge a) show that for every edge $e$ of $G$ and for every orientation of $e$, there exist an orientation of the remaining edges of $G$ such that the ...
0
votes
3answers
39 views

Chess Board Coloring of a Paper using an Arbitrary Curve

Pick a piece of paper and a pen. Put the pen on a starting point and begin to draw an arbitrary curve and don't withdraw your hand until you reached the starting point. You can meet your curve during ...
0
votes
1answer
52 views

A graph with infinitely many distinct cycles

I am trying to show the following statement, but I can't. If a graph contains infinitely many distinct cycles then it contains infinitely many edge-disjoint cycles.
0
votes
2answers
29 views

Can I use Dijkstra's Algorith for finding ALL shortest paths?

Suppose I know by promise that there are lots of paths from $v_s$ to $v_e$ in some graph $G \ni v_i$. Is there a way to modify Dijkstra's algorithm to find all shortest paths rather than just one ...
0
votes
1answer
32 views

How to prove that graph has cycle?

Let $(V,E)$ be a graph where between each two vertices $v_1,v_2\in V$ there exists only one path. Then The graph has no cycles. Adding a new edge creates a cycle. I have no idea how it could be ...
0
votes
1answer
48 views

Convert a tree to a forest where every component has an even number of vertices.

I have the following problem, which I am struggling with. It asks to find the maximum number of edges to be removed from a tree to convert it to a forest, where every component will have an even ...
0
votes
1answer
26 views

How to prove $G$ is not Hamiltonian?

A connected graph $G$ of order $n=2k+1$ has $k+1$ vertices of degree 2, no two of which are adjacent, while the remaining $k$ vertices have degree 3 or more. Show that $G$ is not Hamiltonian.
0
votes
2answers
53 views

How to prove that the diameter of a graph is less than 2 given that the minimum degree of any vertex in G is greater than the number of vertices / 2

How do I prove the following statement. Let $G = (V,E)$ be a graph. Prove that if $δ(G) \ge \frac{|V|}2$, then $\operatorname{diam}(G) \le 2$ I believe $\delta$ is minimum degree of any vertex ...
0
votes
1answer
22 views

What is the length of the longest decreasing sequence in integer matrix?

Given a finite $m \times n$ matrix $M$ with all distinct integers, we travel it following two simple rules: The travel can start from any cell, say, $M[i,j]$. At each cell $M[i,j]$, it computes the ...
0
votes
1answer
24 views

Calculating the “edge” distance between two points

I was wondering if measuring the "edge" distance $d_e$ between two points like this had a formal name, and if it could be calculated directly? In both examples you are not allowed to cross diagonally ...
0
votes
1answer
35 views

Proving two graphs are isomorphic in polynomial time - Bondy/Murty - Graph Theory Page 6

I am trying to do the below problem: Now I can't see how one does this. I know you can explicitly show the bijections, but I can't see an easy way to do this, since it is $3\text{-regular}$. I ...
0
votes
2answers
25 views

A simple problem of graph theory about the degree of vertices.

A graph has $7$ vertices and $10$ edges then which is true? $(I).3$ vertices of degree $4$ and $4$ vertices of degree $2$. $(II).2$ vertices of degree $5$ and $5$ vertices degree $2$. $(III).$Every ...
0
votes
2answers
24 views

Is the path between 2 vertices of a Minimum weight tree of a graph the shortest path between those 2 vertices?

Suppose we have an undirected, connected graph, $G_1$ If you have a minimum weight spanning tree $G_2$ for graph $G_1$. Is it possible to find two vertices in $G_1$ which is has a shortest path that ...
0
votes
1answer
44 views

Soundness of a simple tree edge count proof by induction

I'm trying practice and get better at proofs. Here is my attempt at a proof of the following simple statement: There are $n-1$ edges in a $n$ vertex tree. We will prove this by induction on $n$ ...
0
votes
1answer
24 views

Is the derivative of the characteristic polynomial equal to the sum of characteristic polynomial of principle submatrices?

Let $A$ by an $n \times n$ matrix over the complex numbers and let $\phi(A,x) = \det(xI-A)$ be the characteristic polynomial of $A$. Let $B_i$ be the principal submatrix of $A$ formed by deleting the ...
0
votes
1answer
24 views

how to show that list chromatic number for this graph is 3?

consider the bipartite graph shown below,how should I show that list chromatic number for this graph is 3? because it is bipartite the chromatic number is 2,and because $\chi _{L}(G) \geq \chi(G)$ ...
0
votes
1answer
26 views

Planar Graph: external/unbounded face

G is a planar graph. E is an arbitrary edge of G. "There exists a planar drawing of G where E is on the unbounded face of the drawing." Why is the above statement true? Any help is appreciated.
0
votes
2answers
30 views

Are there algorithms that traverse from two sides of a graph to find an s-t path.

Say I have a directed graph with a source and destination node s and t and I want to see if there's a path that exists between those two nodes. Intuitively I would think that the fastest way to do ...
0
votes
1answer
21 views

Planarity Criterion

I am looking for a proof of the theorem: If a planar graph, $G$, has $v$ vertices ($v \geq 3$) and no cycles of length 3 then, $e \leq 2v-4$. I remember doing this in a graph theory course and I ...
0
votes
2answers
13 views

Why does eigenvalue k of a regular graph of degree k have a multiplicity of one

Motivation There are lots of questions on here which link the "connectedness of a k regular graph and the multiplicity of its k eigenvalue", I understand their logic apart from the fact that they ...
0
votes
1answer
17 views

Isomorphism between graphs with coloured edges

I have two graphs with verteces numbered from $1$ to $7$ and coloured edges. When can I say that these two graphs are not isomorphic? Can someone give me the definition? Thanks!
0
votes
1answer
27 views

Complement of the complete bipartite graph

Hey taking the complement of the complete bipartite graph $K_{m,n}$ I think that I get a disconnected graph composed of the complete graph $K_m$ and the complete graph $K_n$ is that right?
0
votes
1answer
66 views

Graph diameter and average pairwise distance

How do I prove that for a graph G, I can always find a constant c>0 such that $$ \frac{diameter(G)}{average \ pairwise \ distance (G)} > c $$ where $$ average \ pairwise \ distance = ...
0
votes
1answer
20 views

How can I show complete graphs are determined by spectrum?

I understand how to prove a complete graph $K_n$ has spectrum $\lbrace -1^{(n-1)},n-1 \rbrace$. However I am having difficulty proving that the spectrum uniquely determines the complete graph. ...
0
votes
2answers
31 views

In a Complete graph, prove $ \sum n_{i} = n, then { n_{i} \choose 2 } \le { n \choose 2 } $

I'm studying graphs in algorithm and complexity, but I'm not very good at math. In a Complete graph, prove $ \sum n_{i} = n, then { n_{i} \choose 2 } \le { n \choose 2 } $ ? please give some ideas.
0
votes
2answers
72 views

All self-complementary trees [closed]

I am looking for all self-complementary trees. Could someone accompany me in this great adventure?
0
votes
1answer
90 views

Algorithm producing a minimum spanning tree?

I need to prove that the following algorithm produces a minimum spanning tree(MST) upon termination. I think, looking at the lecture notes, that I need to reduce the operations to red and blue rules ...
0
votes
2answers
43 views

Length of shortest path that visits every vertex

Suppose I have a connected graph with $n$ vertices and start in some arbitrary vertex $u$. I want to visit every vertex of the graph. I do not care about returning to where I started, and I can visit ...
0
votes
1answer
23 views

Connected Graph and its property [closed]

Let $G$ be a connected graph or order $n$, and suppose $1\leq k\leq n$. Show that $G$ contains a connected subgraph of order $k$.
0
votes
1answer
39 views

Graphical sequence proof.

Show that for every finite set $S$ of positive integers, there exists a positive integer $k$ such that the sequence obtain by listing each element of $S$ a total of $k$ time is graphical. This is one ...
0
votes
1answer
70 views

Induction proof for a k-regular graph

so I've come across a weird problem. I've learned about induction before, and when it's an equation I can generally do them. However, this problem I'm having trouble with: "A k-regular graph is an ...
0
votes
1answer
30 views

Probabilistic method in coloring of graph

I was reading Noga Alon's Probabilistic Methods and came across this question which I am unable to prove. There is a two-coloring of $K_n$ where $K_n$ is a complete graph of $n$ vertices with at most ...
0
votes
1answer
33 views

Is this a correct planar graph testing algorithm?

I want to know whether the below algorithm is correct for testing planr graph: step 1. Remove every degree-1 vertex and the edge that contains it. step 2. Remove every degree-2 vertex and replace ...
0
votes
1answer
31 views

Graph homomorphism, and how to proof?

I want to know whether there exists a homomorphism from this graph (below in the image) to $K_5$ (complete graph with 5 vertices). If so, how can I prove this relationship? Since homomorphism is a ...
0
votes
1answer
37 views

Labelled graph minor theorem

Note: this isn't duplicate to this: Does the Robertson-Seymour theorem apply to vertex-labeled graphs? One of equivalent definitions of graph minorship is the following: $G_1$ is minor of $G_2$ if we ...
0
votes
2answers
68 views

Determinant of identity minus adjacency matrix

Let $M$ be the adjacency matrix of a directed graph $G$. Is there any known relation between $\det(\textrm{id}-M)$ and the cycles of $G$? It is easy to see that if $G$ is acyclic then this ...
0
votes
1answer
42 views

Showing exitence of a path in Graph Theory

If $P$ and $Q$ are paths in a connected graph that have no vertices in common, then there exist vertices $u$ and $v$ and a path $P′$ such that $u$ is on $P$, $v$ is on $Q$, $P′$ is a $u–v$ path, ...
0
votes
1answer
30 views

Hamiltonian cycle adjacency sum Proof

Let $C$ be a Hamiltonian cycle on a graph with vertices labeled {$1,...,9$}. Prove that there are $3$ vertices adjacent in $C$ whose labels sum to at least $12$. I understand why this fact is true by ...
0
votes
1answer
24 views

Proof about spanning tress in graphs

Let $G=(V,E)$ be a graph and $T_i=(V,F_i),i=1,2$ two disjoint spanning trees in $G$. Let $f_1 \in F_1$. Prove that there is $f_2\in F_2 $ such that $T:=T_1-f_1+f_2$ is a spanning tree.
0
votes
2answers
147 views

Number of edge disjoint Hamiltonian cycles in a complete graph with even number of vertices.

In a complete graph with $n$ vertices there are $\frac{n−1}{2}$ edge-disjoint Hamiltonian cycles if $n$ is an odd number and $n\ge 3$. What if $n$ is an even number?
0
votes
2answers
58 views

Prove that if G is a tree in which all vertices have odd degree then G has odd size.

Prove that if G is a tree in which all vertices have odd degree then G has odd size. Good night, do not know how to approach this "prove". Can you give me tips to solve it?. Please.
0
votes
2answers
33 views

Proof d-regular graph has an equal number of vertices in its bipartition

Let $G$ be a $d$-regular graph. Suppose that $G$ is bipartite with bipartition $(A,B)$. Prove that if $d>0$ then $|A| = |B|$. Also why is this statement false when $d=0.$ I'm not sure how to show ...
0
votes
2answers
50 views

Graph Theory, with algorithms like kruskal and something more

The new government of the archipelago of Sealand has decided to join six islands by bridges to connect them directly. The cost of building a bridge depends on the distance between the islands. This ...
0
votes
1answer
28 views

Generators Trees in a Tree

My question is very short: How many spanning trees have a tree? Thanks in advance