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
0answers
16 views

Undirected graphs and possible vertex relationships

Given an undirected graph with visible vertices but hidden edges, and with rules such as: node A connects with at least 2 other nodes node B connects with at least 1 other node node C connects with ...
1
vote
1answer
38 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
33 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 ...
0
votes
0answers
23 views

How to generate a list of representatives of graph isomorphism classes for small graphs?

I am trying to verify, using a Python program, that a conjecture about graphs holds, at least, for small graphs. In order to do this, I'm looking for a way to quickly generate a representative for ...
1
vote
2answers
23 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 ...
1
vote
2answers
46 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. ...
1
vote
1answer
40 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 ...
1
vote
1answer
114 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 ...
0
votes
1answer
32 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
0answers
29 views

Graph algebra papers

The following graph multiplication appears to be quite natural: Let $g_1=(V_1,E_1)$ and $g_2=(V_2,E_2)$ be two graphs ($V_i$ are sets of vertexes and $E_i$, sets of edges). Intuitively, the product I ...
0
votes
1answer
18 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
49 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
12 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 ...
2
votes
2answers
48 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
25 views

Shape of graph for co-purchased items

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

Let G be a graph on 10 vertices of degrees 1,1,2,3,3,3,4,4,5,8. How many paths of length 2 does G contain?

Let G be a graph on 10 vertices of degrees 1,1,2,3,3,3,4,4,5,8. How many paths of length 2 does G contain? Note: path of length 2 means of the form a-X-b, where a and b do not have to be distinct ...
2
votes
2answers
25 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 ...
1
vote
3answers
48 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
0answers
34 views

Expected number of steps in a random graph walk

Suppose I have a directed graph $D(V, A)$ where the edges have weights on them. Let's notate the weight function $w: A \rightarrow [0, 1]$. If $f, t \in V$ and $a \in A$ such that $a = (f, t)$ then ...
0
votes
1answer
16 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
54 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
0answers
24 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 ...
-2
votes
1answer
23 views

What is the relation between max independent set problem and coloring problem? [closed]

Is there any difference or relation between size of independent set and coloring problem?
0
votes
0answers
40 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 ...
0
votes
1answer
23 views

Preferential Attachment and salton similatiy 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 ...
0
votes
0answers
21 views

Eigen vectors of graph laplacians

I have been reading about spectral graph theory from Daniel A. Spielman's notes. Fiedler’s Nodal Domain Theorem from this note says that : Let $G = (V, E, w)$ be a weighted connected graph, and let ...
1
vote
0answers
21 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 ...
1
vote
1answer
42 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
32 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 ...
0
votes
0answers
23 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
29 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 ...
0
votes
0answers
32 views

Graph theory matching question.

There are $n$ children and $n$ toys in a room. Each child wants to play with $r$ specific toys and for each toy, there are $r$ children who want to play with that toy. Prove that we can organize $r$ ...
2
votes
1answer
28 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$ ...
2
votes
1answer
29 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
35 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
40 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 ...
0
votes
1answer
42 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 ...
1
vote
1answer
50 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
50 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
26 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
votes
0answers
20 views

Graph Theory: Bipartite

Show that a bipartite graph G has a perfect matching if and only if |N(S)|≥|S| for all S⊆V. I am having trouble getting this problem started. Could someone help me with this please. Thanks
0
votes
2answers
30 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
33 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
0answers
13 views

Detect Regions Described By Lines in Rectangular Coordinates

Need some help from the superior math minds here. This problem is part of a software project. Essentially, I have a Cartesian grid. The user can create lines by plotting points (every 2 points ...
0
votes
1answer
22 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
35 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 ...
0
votes
1answer
35 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
18 views

Partition of the node set of a graph into connected subsets

What word is most commonly used in graph theory for a partition of the node set of an undirected graph into connected subsets? More rigorously: Given an undirected graph $(V,E)$, a partition $S ...
-1
votes
0answers
14 views

A Separable graph on 4 vertices

Can we construct a nonseparable graph on 4 vertices each vertex of which has degree at least four and at least two distinct neighbours, and in which splitting off any two adjacent edges results in a ...
0
votes
0answers
33 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 ...