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

Splitting graphs into disjoint sets by removal of edges

You have to split the graph into two disjoint sets such that every vertex in a set has only one vertex connected to it from the another set .That is,after doing the operation,you'll have all the ...
1
vote
0answers
90 views

minimum strength of the edges occurring in any path P

Let $G=(V,E)$ be a graph and let $s: E \to \mathbb{R}^+$ be a function. Let us call $s(e)$ the strength of the edge $e$. For any path $P$ in $G$, the reliability of $P$ is, by definition, the minimum ...
0
votes
1answer
93 views

Existence of a Perfect matching in a Graph

how to find whether a given graph has a perfect matching or not?? I read that the degree should be atleast n/2 for all the vertices to be a perfect matching..But can anyone give the necessary and ...
1
vote
1answer
79 views

Claw free Graph

I have been reading this wiki article on how to find if the graph is claw-free or not but I cannot understand some part of it. Algorithm says(Under the recognition title) "...one can test whether a ...
1
vote
1answer
284 views

A bipartite graph with the degree sequence {5,5,5,5,5,8,8,8,8,8,8,8,8,9}

Does there exist a simple bipartite graph with the degree sequence {5,5,5,5,5,8,8,8,8,8,8,8,8,9}? I believe the answer is no but cannot prove this. Any assistance will be appreciated. Thanks
2
votes
0answers
87 views

Perfect Matching of fixed edge in bridgeless cubic graph

My question: In bridgeless cubic graph $G$, given an edge $e_1$ in $G$, Prove that there exist a perfect matching contain the given edge $e_1$. Given two edges $e_1,e_2$ with the distance between ...
1
vote
1answer
66 views

Characterize graph by its connectivity matrix

Let $A$ be an $n\times n$ symmetric matrix, all of whose entries are $1$ or zero. Such a matrix is associated with an undirected graph $G$ with $n$ nodes, in which there is an edge between ...
1
vote
1answer
124 views

N- dimensional hypercube graph problem

So I have this problem: Prove that the n-dimensional hypercube is a bipartite graph for every n bigger or equal to 2. All help is welcomed.
2
votes
2answers
50 views

Question on connected graphs

Is it true that if for each partition of a graph G's vertices into two non empty sets there is an edge with end points in both sides then G is connected? Intuitively this seems true to me. But I ...
7
votes
1answer
344 views

$G$- simple graph. Show that it has a path of length at least $\dfrac{2m}{n}$ where $m=|E|$ and $n=|V|$

Let $G$ be simple graph. I need to show, that it has a simple path of length at least $\dfrac{2m}{n}$ where $m=|E(G)|$ and $n=|V(G)|$. I tried induction on $n$. Then With $n=1$ we have single vertex ...
0
votes
2answers
174 views

I do not know how to proof this. An undirected graph *G* with *n* vertexes is connected if that graph has more than `(n-1)(n-2)/2` edges.

I do not know how to proof this. An undirected graph G with n vertexes is connected if that graph has more than (n-1)(n-2)/2 edges.
0
votes
3answers
295 views

Acyclic graph - source node

How can I prove that a directed acyclic graph has a source node? A node 'a' is called source node if doesn't exists edges like ('b','a').
1
vote
1answer
78 views

Is it possible to solve the shortest path problem by hardware? And is it worth it?

Okay, I recently thought of an idea. Suppose given any map you create an equivalent circuit where there are same number of vertices (intersection of wires) and length of the path is proportional to ...
1
vote
0answers
79 views

Showing that two given graphs are homeomorphic

I won't to verify whether the two graphs given above are homeomorphic. I am not sure of the method to verify this. I would much appreciate if anyone could give some assistance. Thanks
1
vote
0answers
405 views

Area optimization: Packing rectangles inside rectangle

Background: I am scrambling to figure out the optimization algorithm to build sprite image, which is essentially a big container rectangular image, with multiple rectangular images. I have found an ...
2
votes
2answers
376 views

Finding characteristic polynomial of adjacency matrix

Short question im having a tad difficulty with. I'm trying to find the characteristic polynomial of a graph that is just a circle with n vertices and n edges. I think the adjacency matrix should ...
1
vote
0answers
74 views

Finding the diameter of a graph with a complex structure

I know the diameter of the above graph is 6. But I don't know a formal way of doing this. However I know it is possible to draw a matrix considering the minimum distance between the vertices but ...
5
votes
2answers
936 views

Mantel's Theorem proof verification

I found the following proof for Mantel's proof. I cannot understand the equality that I have highlighted in the image was arrived at. I would appreciate some assistance thanks
0
votes
2answers
78 views

Problem about Number of Distinct Hamiltonian Cycles in $K_9$

I am asked to find the number of distinct Hamiltonian cycles in the complete graph $K_9$ where no two of them have an edge in common. I came up with the following combinatorial argument but am very ...
0
votes
2answers
367 views

Graph theory people at a round table problem

So I have this problem: There are 20 people at a party and each one of them is friends with at least 10 of the people. They all sit at a round table. Prove that there is a way to place the people on ...
1
vote
2answers
424 views

Perfect Matching in a non-bipartite graph

I need to find out if you can have a perfect matching in a given graph, with $n$ vertices and $m$ edges and $1\leq n,m\leq 100$. I want a complexity of $O(n)$ if possible. I only need to know if there ...
3
votes
1answer
6k views

How to draw all nonisomorphic trees with n vertices?

I have a textbook solution with little to no explanation (this is with n = 5): Could anyone explain how to "think" when solving this kind of a problem? (for example, drawing all non isomorphic ...
1
vote
1answer
58 views

A dimension of graphs

I have searched definitions of the dimension of a graph but I haven't found what I'm looking for. Has anyone considered the minimal dimension of the ambient space for the geometric representation of ...
3
votes
1answer
324 views

Expected number of vertices a distance $k$ away in a random graph?

Given a random (undirected and unweighted) graph $G$ on $n$ vertices where each of the edges has equal and independent probability $p$ of existing (see Erdős–Rényi model). Fix some vertex $u\in G$. I ...
1
vote
1answer
65 views

Weighted Set covering problem with a fixed number of colors

I have a set of elements U = {1, 2, .... , n} and a set S of k sets whose union form the whole universe. Each of these sets is associated with a cost. I have a fixed number of colors, C = {1 , 2, ...
0
votes
2answers
880 views

Undirected graph 1 degree checking

Given an undirected graph, which consists of n vertexes and m edges. Provided we can delete edges from the graph. Now we want to check is it possible to delete edges in the graph so that the degree of ...
1
vote
1answer
323 views

Belief Propagation Algorithms for Graphical Models with Cycles?

Belief propagation algorithms cannot solve for the probabilities of a cyclic graphical model; they only work for acyclic graphical models. For undirected graphical models (for example Markov random ...
0
votes
1answer
72 views

Help on 1-regular graphs!

I have this for my homework. Given a graph, I can remove any number of edges in order to form a 1-regular graph or state that it's impossible. I tried some different approaches but I can't cover all ...
3
votes
2answers
717 views

Finding the diameter of a n-cube

Is there a general method that can be used find the diameter of a n-cube? In particular what if I want to find the diameter of a 4-cube can someone suggest me a method or hint. I would much appreciate ...
0
votes
1answer
83 views

Number of spanning trees by different formula

my task is to prove that number of spanning trees in complete graph on 4 vertices is 16 using by this formula: K(G)=K(G\e)+K(G/e) ( G\e means subtraction of an edge and G/e means contraction of an ...
0
votes
0answers
71 views

A toroidal graph to identify (with illustration)

I posted this before, was asked for a diagram because I only had a confused prose description, and by the time I added the diagram I believe the thread had long disappeared from the first few pages ...
0
votes
2answers
580 views

Cycle containing two given nodes in an undirected graph

Given an undirected graph G=(V,E) and two nodes s, t in V, how to FIND an arbitrary SIMPLE cycle (each node used only once) between s and t? Or just DETECT whether there is a cycle between them? Here ...
3
votes
2answers
424 views

Unique maximum flow

Is there an efficient algorithm for determining whether or not a flow network has an unique maximum flow. I do not mean the actual value (which of course is unique) but the function $f : E \to R$ that ...
1
vote
2answers
35 views

detecting dynamic parts in graph

I have set of (x,y) points which can be connected to form a graph, my goal is to detect dynamic parts of this graph. by dynamic I mean ranges where the values are not stable but they are changing by ...
1
vote
1answer
48 views

Is there a name for connected graphs $G$ in which every vertex $v$ has a unique vertex $v'$ at distance $d$ where $d$ is the diameter of $G$?

Alternatively, what is known about such graphs? Examples are cycle graphs $C_{2n}$ as well as the Platonic graphs (except of course the tetrahedral graph $K_4$).
2
votes
2answers
204 views

Clarifying Dirac's theorem

Theorem : If $G$ is a simple graph with $n$ vertices with $ n ≥ 3$ such that the degree of every vertex in G is at least $ n/2$, then $G$ has a Hamilton circuit. In this if $n$ is odd, should I ...
0
votes
1answer
108 views

Positioning Points Based On Distances (Intersecting Circles)

I have a series of points, which represent mobile devices within a room. Previously I have systematically emitted a ping from each and recorded the time at which it arrives at the others to calculate ...
1
vote
0answers
65 views

Necessary and sufficient condition for an Euler circuit

I have come across the theorem A connected multigraph with at least two vertices has an Euler circuit if and only if each of its vertices has even degree. I just want to know whether the same holds ...
2
votes
0answers
100 views

Can you identify this graph

Could someone identify this graph for me? I apologise for the lack of technical vocabulary, I hope I can describe this clearly enough nonetheless. The graph is formed by the vertices and edges of a ...
1
vote
0answers
119 views

Expansion of subsets of a hamming ball in hypercube

Consider a hypercube graph $G_n = (V,E)$ in n dimensions. Let $H_{1/2} \subset V$ be the set which represents the hamming ball of radius $n/2$. That is for every $v \in H_{1/2}$ the hamming weight of ...
1
vote
1answer
48 views

A List of Graphs on Small Vertex Sets?

I am preparing for the exam of a first year introductory course on Graph Theory. 50% of the paper unfortunately consists multiple choice questions which are at times tricky. They do not necessarily ...
0
votes
2answers
200 views

3-dimensional cube shortest path question

Let Q be the graph consisting of vertices and edges of a 3-dimensional cube. Two relations are defined on the vertices of Q. • R1={(v,w):the shortest path from v to w has an odd number of edges}. ...
-1
votes
2answers
58 views

Eulerian graph has no bridges

my problem is to prove that Eulerian graph has no bridges. Can please anyone help me with that? Thank you!
1
vote
2answers
67 views

A $C_3$ free graph, degrees inequality

If $G$ is a $C_3$ free graph, for any edge $(x,y)$ of $G$ I need to prove that $$\deg(x)+\deg(y)<|V(G)|+1.$$Any hints/answers will be much appreciated. Thanks
1
vote
0answers
96 views

Find all 'big' cycles in an undirected graph

I am unfamiliar with graph theory and hope to get answers here. My goal is to find all 'big' cycles in an undirected graph. A 'big' cycle is a cycle that is not a part of another cycle. (Compare with ...
1
vote
1answer
122 views

Implementing sum product belief propagation

While implementing a stereo belief propagation algorithm, it is required to transform the unary and pairwise energy terms (that one comes across in graph cuts) as negative exponent of e. It is done as ...
0
votes
1answer
208 views

Triple systems with no six points carrying three triangles

Can anyone please send a link to this article? ...
2
votes
1answer
61 views

graph with a bridge

Please help me with the Proof that every graph with a bridge has at least 2 vertices of odd degree. I was thinking about contradictio, to show that if graph contains only vertices with even degree ...
0
votes
2answers
87 views

Which algorithm is this?

I am studying for the exams and I am looking at my notes, where I came across with an algorithm, but there is no title, so I don't know which algorithm it is and it doesn't also exist in my textbook. ...
0
votes
1answer
39 views

Theory of graphs, least possible number of edges with k-components.

I am just preparing for my exams from discrete mathematics, and really dont know how to proove that the least possible number of edges of graph with n vertices and k components is n-k. Can anybody ...