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

1
vote
0answers
61 views

2 simple doubts about graph theory problems

The first one: In this exercise I am asked to compute the number of 4-regular graphs of order 7. I had an idea but I don't really know if it is the correct way of proceeding: In a graph of order 7, ...
1
vote
0answers
201 views

Every Edge of a graph is either Contractible or Deletable

I need to Show that Every edge of a 2- Connected graph is either contractible or Deletable. Contractible Edge:- To contract an Edge, remove it and its end points(vertices) should be merged along with ...
1
vote
0answers
60 views

Under what conditions is there a common transversal?

Let $S = \{S_1,\dots,S_n\}$ and $T = \{T_1,\dots,T_n\}$ be two collections of finite subsets of $\{1,2,\dots\}$. A transversal for $S$ is a list of elements $s_1,\dots,s_n$, one coming from each ...
1
vote
0answers
579 views

Can I use Strong Induction to prove graph theory? - Hamilton Path/Tournament Graphs

I am working on the below proof. I am still new to proves so I am wondering if you guys can answer the following questions: 1) Did I use the inductive hypothesis correctly here? (By the inductive ...
1
vote
0answers
46 views

showing that all convex polehedron graphs are 3-connected

I'm trying to figure out how to show that two nonadjacent vertices in the graph of a convex polyhedron can be disconnected from one another by the removal of at least three vertices. I know what a ...
1
vote
0answers
37 views

Conditional covariance in gaussian graphical models

I have a hypothesis, but I'm not sure if its true. The Wikipedia page states that if the covariance matrix is given by $$\Sigma=\left[\begin{matrix} A & B \\ B^T & C \end{matrix}\right]$$ ...
1
vote
0answers
48 views

Number of nodes with degree d in a graph

Why the number of nodes with degree $d$ in a graph $G$ is equal to the number of copies of $d$-stars in $G$ that are not part of any $(d + 1)$ star in $G$ ? Isn't it possible to have nodes with ...
1
vote
0answers
67 views

Prove that the minimum of row sums of a nonnegative symmetric matrix is preserved

Let $A$ be an $n\times n$ adjacency (nonnegative, irreducible and symmetric) matrix with zeros on the diagonal. Denote $i$-th row sum of $A^k$ as $r^{(k)}_i$, where $k\geq1$. I want to prove that if ...
1
vote
0answers
56 views

Algorithmically constructing graphs with specified degrees

In graph theory books there are lots of problems similar to these: Construct a graph of 7 vertices with exactly 5, 2, 1, 1, 1, 1, 1 degrees Prove or disprove that there is graph of 4 vertices with ...
1
vote
0answers
70 views

A question regarding a prefix code

Let $C=\{ c_1, c_2, \dots, c_m \}$ be a set of sequences over an alphabet $\Sigma$ and $|\Sigma|=\sigma$. Assume that $C$ is a prefix-free code, in the sense that no codeword in $C$ is a prefix of ...
1
vote
0answers
26 views

Genus of a simple graph $G$.

Let $G$ be a simple graph with set of vertices $V(G)=\{a_i,v_j \mid 1\leq i \leq 5, 1\leq j \leq 4\}$ and the set of edges is ...
1
vote
0answers
96 views

Proof of Gallai's Theorem for Critical Graphs

A fundamental theorem in Graph theory is the following: Let $G$ be a $k$-critical graph with $k\geq 4$ and $G\neq K_k$. Then every block in the subgraph of $G$ induced by the vertices of degree $k-1$ ...
1
vote
0answers
224 views

Detect an odd-length cycle from a directed graph

so my goal is to detect an odd-cycle in a directed graph. I know for the undirected graph, the graph contains the odd-cycle iff it's non-bipartile. So I can check whether or not the graph is ...
1
vote
0answers
42 views

Graph diameter of a single vertex?

Convention-wise, given the simple graph with a single vertex, what is the graph diameter? I can see three options, zero, since there is a trivial path from the vertex to itself. infinity, since ...
1
vote
0answers
75 views

Probability that the network is connected in an unstructured p2p network

Suppose that three nodes form an unstructured p2p network (a network where each node has a list of neighbors node, in which there are addresses of c live neighbors) and each selects to cache the IP ...
1
vote
0answers
114 views

Is the singleton graph 2-connected?

Whether the singleton graph is connected, depends on the definition: (1) A graph is said to be connected if every pair of vertices in the graph is connected. (Wikipedia, Connected graph) ...
1
vote
0answers
20 views

On Special Deviations of a Score Sequence

Can anyone help me to my problem? First of all, I will introduce the definition of deviation sequence, and special deviations. Let $<S_1,...,S_n>$ be any sequence of integers. The ...
1
vote
0answers
155 views

Adjacency matrix of directed graph

I am given adjacency matrix $A$ of directed graph. $A(x,y)$ counts the number of edges from $x$ to $y$. I want to show that if $A$ has constant outdegree $d$: (i) For any eigenvalue $\lambda$, we ...
1
vote
0answers
54 views

How can I prove that a particular family of graphs is integral?

I'm working with an infinite family of graphs that seem to always have all integral eigenvalues, and I'd like to find some way to prove that (if it's true). Call the graphs $G_{n,k}$ and define them ...
1
vote
0answers
36 views

Number of Isolated Edges in G(n,p)

I am attempting to find the number of isolated edges in the Erdos - Renyi graph G(n,p). I need to find the formula for the expected number of isolated edges. I've broken the equation down into ...
1
vote
0answers
37 views

Determine the condition on $n$ for $W_n$ to be critical graph.

The way my professor defines $W_n$ is the wheel graph of $n + 1$ vertices. That is, the graph with $n$ vertices, each adjacent to the vertex of degree $n$, in the cycle. We assume $W_n$ is a simple ...
1
vote
0answers
165 views

Set Theory , Konig's Lemma and Infinite Graph Theory

I am trying to understand the basics of Infinite Graph theory and various preconditions in Konig's Lemma. The texts I have studied tend to use the Axiom of Choice (usually Zorn's Lemma) as a tool of ...
1
vote
0answers
50 views

How do I apply vertex or edge coloring to my DAG problem?

I am working on solving a DAG (Directed Acyclic Graph) problem and the part I care about is edge direction and how many ways I can assign directions (while staying acyclic) without making a ...
1
vote
0answers
68 views

Proof of existing path on Depth-First-Search spanning tree

Let $G$ be an undirected connected graph, and $T$ the directed spanning tree of $G$, which I got by performing a DFS on $G$. If $H$ is a complete subgraph of $G$, how can I proof that there a path in ...
1
vote
0answers
48 views

How we show primitive action shows alternating group

I have a graph (as shown in figure), which represents a quotient of the group $$G=\langle A,B,C,D; A^3=B^2=C^3=D^2=(AC)^2=(AD)^2=(BC)^2=(BD)^2=1 \rangle.$$ I proved that $G$ acts 2-transitively and so ...
1
vote
0answers
32 views

Probability of inter-group links in a network with maximum degree 1

In an undirected network, there are two groups of nodes. Group 1 has N1 nodes, and group 2 has N2 nodes. The links in the network are generated following such rules: (1) The maximum degree is 1, ...
1
vote
0answers
399 views

Finding a spanning tree using exactly k red edges in a graph with edges colored by red/blue in linear time.

So we have a graph $G$ with its edges colored by red and blue. we are asked to find a deterministic linear time algorithm that given a parameter $K$ finds a spanning tree of G using exactly $K$ red ...
1
vote
0answers
83 views

References for Hyperbolic Graph Theory

I'm sorry to disturb you but I really got stuck! I can't find any clear and, somewhat, complete reference for this topic. I'm looking for a book, or review, or survey or course notes regarding ...
1
vote
0answers
68 views

Matchings in $G=(V,E)$ be an undirected graph, and let $S,T\subseteq V$ be two sets of vertices with no common neighbors

Let $G=(V,E)$ be an undirected graph, and let $S,T\subseteq V$ be two sets of vertices with no common neighbors (there can be edges between $S$ and $T$). We need to show that if there exists a ...
1
vote
0answers
49 views

pierre simon laplace and his knowledge of the (Laplacian) matrices

so as we all know, there is a graph matrix called the Laplacian that is used in some eigenvalue/eigenvector/graph theory/spectral theory problems. i'm wondering if the name of this matrix is ...
1
vote
0answers
37 views

How to show that the spectral radius of a binary tree approaches exp(1) as the N tends to infinity?

How can I prove mathematically that the spectral radius of a binary tree approaches e as the number of nodes tends to infinity? I mean it is true that the increase in nodes number is exponential but ...
1
vote
0answers
42 views

Determine the number of simple 7-vertex, 4-regular graph that are pairwise non isomorphic.

I'm taking an introductory graph theory course and I am having trouble going about answering this question. I've been told to look at the graph compliment but I don't quite understand how that ties ...
1
vote
0answers
87 views

zarankiewicz problem lower bound

I was just reading through the following article: http://page.mi.fu-berlin.de/szabo/PDF/stoc96.pdf On page 2 they give an explicit formula for the lower bound of the size of the graph. Summary: We ...
1
vote
0answers
259 views

solutions to flow free game

In flow free, the goal is to connect dots with the same color using pipes, and pipes may not cross. (https://play.google.com/store/apps/details?id=com.bigduckgames.flow) Every square in the grid has ...
1
vote
0answers
289 views

Rigorously prove that a u-v walk implies a u-v path of equal or lesser length .

I am trying to prove the following as an unofficial exercise for a course I'm in: Walks and paths in a graph Prove: For any graph if there is a k-length walk between two nodes, then there exists a ...
1
vote
0answers
29 views

how to prove that every complex circuit is a union of simple circuits

I have an euler circuit in a graph, and I want to prove that in-degree=out-degree. I know that if I can split the original circuit to simple ones, then every simple circuit has in-degree=out-degree. ...
1
vote
0answers
30 views

Can't figure out how to prove Eulerian circuit

I have a graph that is undirected, connected and every vertex has an even degree and I want to prove that a graph like that has a circuit that goes through all edges and only once. I searched the ...
1
vote
0answers
129 views

Upper and lower bound for travelling salesman path.

Let $G$ be a complete graph with weights. $MST(G)$ is the length of it's minimal spanning tree and $TSP(G)$ is the length of minimal travelling salesman path (length I suppose it's the sum of weights ...
1
vote
0answers
38 views

Number of touching triplets in hypersphere packing contact graph

I would like to know what is curently known about the number $N$ of touching-triplets involving a given vertex $V$ in the contact-graph of $d$-hypersphere packings. For $d=2$ and $d=3$, one has $N = ...
1
vote
0answers
49 views

Biconnected graph

Let $P$ be a piece of a bi-connected graph with respect to a cycle $C$. Show that if $P$ has at least one vertex, the number of edges of $P$ is greater than or equal to the number of attachments of ...
1
vote
0answers
72 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 ...
1
vote
0answers
59 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
265 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 ...
1
vote
0answers
56 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 ...
1
vote
0answers
180 views

what are the advantages and disadvantages of Belief propagation

Belief Propagation cannot solve the graphical model which has cycles. For undirected graphical model for example MRF and CRF in computer vision area, in which cases the model has no cycle ? As far as ...
1
vote
0answers
37 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 ...
1
vote
0answers
96 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
89 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
0answers
66 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
0answers
65 views

Does every simple cycle contain at least one back edge?

Soppose we have an udirected, connected graph. Apply the DFS algorithm to find back edges of this graph. Now, I have found a lecture notes saying following : Each back edge (i,j) defines a cycle. A ...