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
34 views

Connectivity of a graph

Lets say that I have a graph that looks like this: What does it mean if I take out one node in this case $6$ is it a valid argument to say that the graph still has $6$ edges? Or that is it an ...
1
vote
1answer
81 views

Extending Euler's Formula for Connected Planar Graphs

I am trying to figure out how to extend Euler's formula, n - e + f = 2, to contain a connected component denoted k. I am new to graph theory so I am not sure if the way I got there is correct or if ...
1
vote
2answers
350 views

number of edges in the complement of a complete bipartite graph as a function of $n$, the toal number of verticies

Consider any complete bipartite graph $K_{p,q}$. Express the number of edges in $K_{p,q}^C$, the complement of $K_{p,q}$, as a function of $n$, the total number of verticies. Now, I know that I ...
1
vote
2answers
39 views

If G is connected and order = size - 1 G is a Tree [duplicate]

to prove that, is it correct to proceed by contradicion and try to reach some conclusion like "if the order = size - 1 there can't be any cycles"? In that case, can you give me a hint of where to ...
0
votes
1answer
68 views

The connectivity of a graph does not exceed its minimum degree

Prove that for every graph $G: \mathcal K(G) \le \delta G$ $\mathcal K(G)$ is the connectivity of $G$ $\delta G$ is the minimum degree of $G$ This is a theorem in Graph Theory that I believe needs ...
2
votes
2answers
91 views

Prove for a simple graph that $n-1 \leq m \leq \frac{n(n-1)}{2}$

For a given simple (that is neither loops nor multiple edges are allowed) undirected graph, where $m$ is the number of edges and $n$ is the number of vertices that the following inequality holds. $$n-...
1
vote
1answer
216 views

Probability that exists at least an edge in the configuration model

In this period, I am studying some topics on random networks to understand the modularity optimization used in community detection. In particular, I am trying to understand a model called ...
2
votes
1answer
450 views

adjacency matching in an undirected graph

I am having trouble understanding this concept, and have not found any good resources on google that explain it in a straightforward manner: An adjacency matching in an undirected graph G is a ...
2
votes
1answer
180 views

A tree has at least two leafs (proof by contradiction)

I would like you to tell me if the proof is correct and how can I improve the formalisation of it. Also, if all the assumptions/steps of the proof are correct. I intend to proof the above statement, ...
0
votes
1answer
190 views

n-degree neighborhood of a node v

I am confused about the definition of the n-degree neighborhood of a node v in a graph. The definition says: "The $n$-degree neighborhood of a node $v_i$ is the set of nodes exactly $n$ hops away from ...
4
votes
1answer
391 views

Degree sequence of connected graphs

Given graph degree sequence . What is the condition that it can be degree sequence of connected graph. Can anyone please share link to theorem?
0
votes
1answer
49 views

Prove that if $G$ is a graph with maximum vertex degree equal 3, then G can be divided into 2 edge-disjoint subgraphs $C$ and $F$

Prove that if $G$ is a graph with maximum vertex degree equal 3, then G can be divided into 2 edge-disjoint subgraphs $C$ and $F$, where $C$ is sum of vertex-disjoint simple cycles and $F$ is a forest....
2
votes
2answers
199 views

Does there exist a simple graph with the degree sequence

Does there exist a simple graph with 7 vertices and the degree sequence {0,2,2,2,3,5,6}? I know that the Handshaking Lemma says that the sum of the degrees is twice the number of edges. In this case ...
0
votes
1answer
37 views

Shape of graph for co-purchased items

I have a database containing orders from a e-commerce site where: ...
2
votes
2answers
30 views

Help with this problem please

I have to proof that in a graph $G$, if $n$ is the order and $m$ the size, if $G$ is connected then $$m \geq n -1.$$ I had thought about doing it by contradiction and then finding that if it is ...
2
votes
3answers
101 views

I need help with this graph proof please

Let $G$ be a self-complementary graph in where $n = 4k+1$ . Prove that there is an odd number of vertices of degree $(n-1)/2$. I dont even know where to start with this. I really need help. Thanks!
0
votes
1answer
25 views

Finding appropriate node labels for directed graphs

I am searching for the correct terminology and a solution for the following problem: Given a directed (hopefully acyclic) graph, assign for each node a number, s.t. the numbers of a path are ...
0
votes
2answers
238 views

Hamilton Graph and Complete Tripartite

1) Consider the complete tripartite graph $K_2,_3,_n$ for $n \ge 3$. Determine for what values of n the graph $K_2,_3,_n$ has a Hamilton path, and for what values of n the graph has a Hamilton cycle. ...
0
votes
1answer
118 views

Find a subset of edges that lie on a simple path between two vertices

I am attempting to implement an algorithm found in a paper. One of the subtasks is: "given a directed acyclic graph $(V,E)$, subset of edges $E' \in E$, and vertices $u,v \in V$, find all edges $e \in ...
0
votes
0answers
159 views

Graph with degree at least >= n/2, how adding one more edge makes it Maximal non Hamilton graph(Dirac's theorem proof for Hamilton graph)

Consider the following part of proof for Dirac's theorem: Theorem (Dirac’s Theorem 1952) If G is a simple graph with n vertices where n>=3 and d(v)>=n/2 for every vertex v of G, then G is Hamiltonian....
0
votes
2answers
73 views

Preferential Attachment and salton similarity in directed networks

Preferential Attachment similarity between two nodes in an undirected graph is the degree of the first node multiplied by the degree of the second node. But what about directed graphs? Which degree ...
1
vote
0answers
50 views

Finding coordinates of nodes in a graph

I have a complete graph in which the edges represent the euclidean distance between the nodes which is known. Assuming a node to be (0,0), I want to find (approximately) the coordinates of other nodes....
1
vote
1answer
70 views

$M_{R^n}$; how to derive $n$ for transitive closure?

When finding the transitive closure of a relation $R$, I convert $R$ into a boolean matrix $M_R$, and find the union between $M_R$ and its powers up to $n$. $$M_{R^*} = M_{R^1} \lor M_{R^2} \lor \...
2
votes
1answer
76 views

Triangulate square with $30$ distinct points inside square

Let $A_1A_2A_3A_4$ be a square, and let $A_5,A_6,A_7,\ldots,A_{34}$ be distinct points inside the square. Non-intersecting segments $\overline{A_iA_j}$ are drawn for various pairs $(i,j)$ with $1\le i,...
0
votes
0answers
27 views

Finding a Hamilton path with divide/conquer [duplicate]

We are given a directed graph $G$ with $n$ nodes and $\frac{n(n-1)}{2}$ edges. For all pairs of nodes $u$ and $v$ in $G$, either directed edge $(u,v)$ or directed edge $(v,u)$ is in $G$, but not both. ...
1
vote
2answers
56 views

$n$ regular graph with $2n$ vertices that doesn't contain triangle must be $K_{n\ n}$

I am trying to prove that $n$ regular graph with $2n$ vertices that doesn't contain triangle must be $K_{n\ n}$(Complete bipartite graph). I have check for $n=1,2$ and need hint for proof for ...
2
votes
1answer
614 views

Clear definition of degeneracy of a graph.

There are at least two questions on this topic but the answers are not clear to me and WiKi link didn't make it any clear either. Could someone please clarify is the degeneracy of a graph $G$ ...
1
vote
1answer
235 views

Isolated vertices perfect matching proof

Prove that a graph $G$ without isolated vertices has a perfect matching if and only if $\alpha'(G)=\beta'(G)$.
1
vote
0answers
81 views

k-sum in weighted DAG

Is there a known algorithm that solves the following problem: Given a directed acyclic graph $G$ with weights on the edges, all nodes have a blue color. We seek to color with red every path $P$ with $...
0
votes
1answer
325 views

Graph theory : How to find edges ??

A simple graph in which each pair of distinct vertices is joined by an edge is called a complete graph. We denote by Kn the complete graph on n vertices. A simple bipartite graph with bipartition (X,Y)...
0
votes
1answer
54 views

Long induced path containing a lot of vertices from a stable set

Is there a simple proof/counter-example for this? If we have a (big) connected graph $G$ with a big stable set $S$ and with bounded maximum degree (read "small"), then there's a long induced path (...
2
votes
1answer
178 views

Prove thoroughly: If the degree of all vertices is greater or equal to $\frac{|V| - 1}{2}$, then the simple graph is connected.

I am struggling to write a good, thorough proof. The proof is supposed to be logically rigorous, correct and complete (e.g. no hidden assumption). Moreover, style is important - the proof should be ...
1
vote
3answers
87 views

Why do the children of a node $n$ in a complete binary tree have indices $2n $ and $2n+1$?

The complete binary tree is breadth-first ordered 1 to $n$ where $n$ is the number of nodes. The thing I cant seem to understand is that why are the children of node $N$ always $2N$ and $2N+1$? For ...
0
votes
1answer
43 views

What are some non planar graphs whose sequence is $(4\,4\,3\,3\,3\,3)$?

I know that in order for the $6$-vertex graph to be non planar, it needs to contain more than $12$ edges. I tried drawing some picture to find the graph, but run out of ideas. It's easy to find the ...
1
vote
2answers
210 views

Graph Theory using Rectangles

Show that it is impossible, using 1x2 rectangles, to exactly cover an 8x8 square from which 2 opposite 1x1 corner squares have been removed. When I do this on paper, it is clear that it is not ...
0
votes
2answers
72 views

Number of labeled graphs of $n$ odd degree vertices

Counting graphs with even degrees! Trouble with formula! This question is about number of labeled graphs of $n$ even vertices. I need hint how to find number of labeled graphs of $n$ odd degree ...
0
votes
1answer
37 views

Geodesic distance in graphs

I'm reading a paper that deals with networks/graphs. In the paper they mention the term 'geodesic distance'. I'm not able to understand what does it mean. I hope if you can explain it to me.
1
vote
0answers
93 views

Distance matrix of connected graph always invertible?

I know there's a question elsewhere about distance matrix for points on Euclidean plane, but I'm not sure if that one was relevant. Anyway, given a connected (simple) graph G with $n$ vertices $v_1,.....
0
votes
1answer
354 views

Calculating Adjacency Matrix

I'm having trouble understanding the concept, I know it is pretty simple but could someone help me out. Assume that I have the following: $V = \begin{bmatrix} 0&0&1 \\ 0&0&1 \\ ...
0
votes
0answers
215 views

Proving this property of a tournament graph by induction?

I am working on practicing proofs by induction. Can you please take a look at the proof below and tell me if I proved it correctly? I am particularly worried about the inductive step. Definition 1....
1
vote
0answers
60 views

Random walk on a graph

For a random walk say from point $x$ to $y$ on a graph, How is the probability of a Random walker reaching point $y$ before returning to $x$ related to the expected of the number of visits to point $...
1
vote
0answers
82 views

automorphisms of the infinite trivalent tree

Let $T$ be the infinite trivalent tree. I want to show that if $\alpha,\beta,\alpha',\beta'$ are vertices of the tree such that the distances $d(\alpha,\beta)$ and $d(\alpha',\beta')$ are equal, then ...
1
vote
3answers
86 views

Error for graph Theory proof

I am looking for an error in the proof but I am not certain about it. Pretty sure it has something to do with how there is not always a cycle of length 3. Theorem 1. For every (undirected) graph $...
1
vote
1answer
118 views

Proof that G - v is a tree

For school we have the following assignment: Let v be a leaf of graph G. Prove that the following two statements are equivalent: (i) G is a tree, and (ii) G - v is a tree. The first thing I ...
3
votes
1answer
260 views

Expectation number of cycles in a Erdős–Rényi random directed graph $G(n,p)$

Let $G \sim G(n,p)$ be a directed Erdős–Rényi random graph with $n$ vertices and the probability $p$ that there is a directed edge between any two ordered pairs of vertices. What is the expected ...
0
votes
1answer
280 views

Cayley's formula for the number of trees(Recursion)

I'm trying to understand the proof by recurcion and induction for the Cayley's formula for the number of trees.While I'm trying to understand it there are some things that I don't get at all. -It ...
0
votes
1answer
66 views

find an algorithm to find MST in linear time while each edge has the same weight

I have been disscussing this problem with a lot of my friends . However no solution has been found. let G= w is a weight function for each e in E w(e)=1 find MST of G in O(|V|+|E|) thanks
0
votes
1answer
66 views

Degeneracy number of a ring graph

The definition of $k-$ degeneracy is not clear to me. Could someone please explain how is degeneracy number different from maximum degree $\Delta G$ of the graph $G$? And second question is, does a ...
0
votes
1answer
49 views

Show that cubic hamiltonian graph is edge-3-colourable.

How can I show that cubic hamiltonian graph is edge-3-colourable?
0
votes
1answer
213 views

Probability of random walk traversal

Consider a random walk on an connected, non-bipartite, undirected graph G. Show that, in the long run, the walk will traverse each edge with equal probability. Note: The walk can traverse each edge ...