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
1answer
105 views

Why no cut-vertices or cut edges in a graph where eccentricity is same for all vertices

I need help to prove the following statement. There are no cut-vertices or cut-edges(bridges) in a graph where eccentricity is same for all vertices. I am getting that if the graph contains a ...
1
vote
1answer
69 views

Is this a complete graph

I know a complete graph must have a edge between every pair of vertices, so I just wanted to make sure whether the below was a complete graph or not? I am guessing it isn't because there is no edge ...
1
vote
1answer
96 views

Network Analyses with Subgraphs

Suppose that I have a graph and I divided it to subgraphs which can be overlapping. I want to use these subgraphs in network analyses like centrality calculation, community detection etc. instead of ...
1
vote
1answer
390 views

How can i convert to the undirected matrix to an directed matrix?

Here A square matrix and first figure(AU) shows undirected connection graph and second one shows directed one.Assume that only i have Au metrix and how can i create Ad metrix from Au matrix in ...
1
vote
2answers
1k views

Is a loop actually a circuit?

If I have a single vertex with a self-loop. Do we call that a circuit? Because we "loop" around itself once?
1
vote
1answer
43 views

Infinite non-self-intersecting paths in graphs

Let $G$ be a graph (of any cardinality). Suppose all its vertices have finite degree. Then does there exist an infinite non-self-intersecting path of an infinite sequence of vertices in $G$? If ...
1
vote
1answer
98 views

Prove $MM^t=A+kI$ for matrices associated to graphs

How can I prove that $MM^t=A+kI$ for incidence matrix $M$ and adjacency matrix $A$ of a $k$-regular graph with $n$ vertices? It is easy to see that $MM^t$ is an $n\times n$-matrix (like $A$), ...
1
vote
1answer
65 views

Ambigous line graph definition

While reading the openbook "Algorithmic Graph Theory " I came by Definition 1.7 which is supposed to define what a line graph is , here is the definition: Definition 1.7. Let $G=(V,E,h)$ be an ...
1
vote
2answers
263 views

Introductory Level Books for Graph Theory

Can anybody please suggest some good introductory level text books on Graph Theory ? Preferably those which don't really require a great pre-requisite background on discrete mathematics, but rather ...
1
vote
2answers
115 views

Total weight of every cycle is even if and only if the total weight of every triangle is even.

Integer weights are written on the edges of a complete graph. Prove that the total weight of every cycle is even if and only if the total weight of every triangle is even. Is there any hints on how ...
1
vote
1answer
101 views

Graph drawn in the 3D euclidean space with no crossings

How do i formulate this proof? Prove that every finite graph can be drawn in the 3D euclidean space with no crossings.
1
vote
1answer
538 views

What is the length of the Minimum Spanning Tree

What is the length of the Minimum Spanning Tree for the following weighted graph? Solution. The length of any minimum spanning tree for this graph (and there is more than one) is 60. The graph and ...
1
vote
2answers
89 views

Some questions on toroidal graphs

The complete graph $K_4$ is planar, and like every planar graph it is also embeddable into the torus. a) Why does $K_4$ count as a triangulation of the sphere, but not of the torus? b) What's the ...
1
vote
1answer
99 views

Ramsey and Random Graph

By considering the random graph G(n,p), show that $$R(4,k)>\left ( \dfrac{k}{3\log k} \right )^{3/2} $$ Improve this bound as much as you can.
1
vote
1answer
74 views

Are graphs with certain degree sequences complete?

Let $G$ be a graph of order $n$. Let $d_1,d_2,....,d_n$ be the degree sequence of the graph (The degrees are arranged in a descending order, therefore $d_1\geq d_2\geq ...\geq d_n$. Suppose that ...
1
vote
1answer
119 views

spanning trees of graphs

Assume we have a simple connected graph G, how would start a prove of the following statement? For any edge of G, there is a spanning tree of G that contans it. I have decided that this is a true ...
1
vote
1answer
153 views

Graph decomposition and union by mathematical notation

(I guess, readers might misguided by my original post, So I modify it) If I have an undirected graph, Could you please help me to describe Decomposing a undirected graph into cycles Cycle breaking ...
1
vote
3answers
1k views

Graph theory notation of path concatenation

I was wondering what the proper notation would be when concatenating paths, written as a sequence of nodes, rather than a set of edges. That is: Given: $$ P = ( x, y, z ) $$ Is it valid to ...
1
vote
2answers
1k views

What is the relationship between Clique, Independent Set, and Vertex Cover?

I'm aware that Vertex Cover and Independent Set are complements of eachother, but I've also heard Independent Set referred to something in relation to Clique; I just don't recall what. It can't be the ...
1
vote
2answers
208 views

A multiple-part question about interpreting powers of the adjacency matrix of a graph

Suppose that we have a group of six people, each of whom owns a communication device. We define a $6\times 6$ matrix $A$ as follows: For $1\le i\le 6$, let $a_{ii}=0$; and for $i\ne j$, ...
1
vote
2answers
209 views

Triangular graphs

I was learning algorithms and data structures, and can't manage with this problem: We say that a graph is triangular when it is undirected, connected and it's each biconnected component is a cycle ...
1
vote
1answer
355 views

Ramsey-type result for tournaments

I'm working on the following questions but with no luck so I was hoping maybe someone can come up with help. Let $T$ be a tournament on $n$ vertices, say $\left\{v_{1},\ldots,v_{n}\right\}$, and let ...
1
vote
2answers
736 views

Graphs such that $|G| \ge 2$ has at least two vertices which are not its cut-vertices

Show that every graph $G$, such that $|G| \ge 2$ has at least two vertices which are not its cut-vertices.
1
vote
1answer
168 views

Blocks of imprimitivity in vertex-transitive graphs

An exercise from a book that I am currently studying asks to show the following. Let $B$ be a block of imprimitivity of $\rm{Aut}(G)$ for a vertex-transitive graph $G.$ Then the graph induced by ...
1
vote
1answer
134 views

Eulerian and hamiltonian graph

I am currently work on a problem about these two graphs I mentioned in the title: The maximum node degree is: $8$ because there are 8 nodes The graph has subgraphs: $8$ because of the 8 ...
1
vote
2answers
5k views

Easiest way to determine all disconnected sets from a graph?

Suppose that I have a un-directed graph of nodes and edges, I would like to know all sets of nodes that do not connect with any other nodes in the graph. Here is a concrete example to help you ...
1
vote
1answer
68 views

Searching the tree, proof

Let $G = (V,E)$ be undirected and connected graph and let $u\in V$. Let $DFS(u)$ and $BFS(u)$ be trees of searching $G$ by algorithms DFS and BFS respectively(starting from $u$). Prove that: ...
1
vote
2answers
130 views

Graph Theory proof

I need to make a proof but I can't come to the solution: For every vertex of oriented graph with vertices $U_{1},U_{2},\ldots,U_{n}$ we've got $s_{+}(U)$ the number of edges, which come to the vertex ...
1
vote
1answer
206 views

Number of paths that begin at vertex, traverse $3$ edges of cube and end furthest

Select a vertex $V$ of a cube. How many paths begin at $V$, traverse exactly $3$ edges of the cube, and end at the vertex furthest from $V$?
1
vote
2answers
916 views

Graph Theory - Hard Question -Finding for what values of n ≥ 2 is it possible to form a domino ring that uses all of the C(n,2) dominoes

A domino is a $2\times1$ rectangle. On each half of the domino is a number denoted by dots. In the figure, we show the ten dominoes whose pairs of numbers correspond to pairs chosen from ...
1
vote
1answer
682 views

$G$ connected planar graph, less than 12 vertices, then $\chi (G) \leq 4$

The problem is: Let $G$ be a connected planar graph with less than 12 vertices. a) Prove that G has a vertex with degree $\leq 4$. b) Prove that $\chi (G) \leq 4$. (Do not use the Four Color Theorem) ...
1
vote
2answers
781 views

Chromatic Polynomial

I am asked the following: Let n be a positive integer at least 3. The wheel W_n is the graph obtained by taking the cycle C_n, placing an additional vertex at the center, and joining it to ...
1
vote
2answers
889 views

Restrictions on the faces of a $3$-regular planar graph

I'm new here and I'm having difficulty with this graph theory question. Suppose $G$ is a connected $3$-regular planar graph which has a planar embedding such that every face has degree either $5$ or ...
1
vote
1answer
190 views

Empty Set Partition of a Bipartite Graph?

My textbook defines a bipartite graph in the following way: A graph $G = (V, E)$ is called bipartite if $V = V_1 \cup V_2$ with $V_1 \cap V_2 = \emptyset$, and every edge of $G$ is of the form ...
1
vote
2answers
181 views

existence of a spanning tree

Let $T$ and $T'$ be two spanning trees of a connected graph $G$. Suppose that an edge $e$ is in $T$ but not in $T'$. Show that there is an edge $e'$ in $T'$, but not in $T$, such that ...
1
vote
1answer
76 views

Why does $S + o(G-S)$ have the same parity as $n(G)$?

I seemed to see this from some place I don't remember In a graph $G$, for any subset $S$ of vertices, $|S| + o(G - S)$ has the same parity (odd or even) as $n(G)$, by counting the vertices ...
1
vote
1answer
190 views

Disconnected graph with degree sequence

Is there a disconnected graph with degree sequence $(4$, $4$, $3, 3, 3, 3, 3, 3)$?
1
vote
1answer
864 views

Monochromatic triangle and edge colouring

$r(k) := R(\underbrace{3,3,...,3}_k)$ (I.e. $r(k)$ is the minimum integer $n > 0$ such that every coloring of edges of $K_n$ in $k$ colors is guaranteed to produce a monochromatic triangle.) Show ...
1
vote
1answer
202 views

Induced subgraph of the Petersen graph

Let $G$ be a Petersen graph and $S\subset V(G)$, how can I compute $e(G[S])$ for non-trivial $S$? Here $G[S]$ is the induced subgraph of $G$ and $e(G[S])$ is the number of edges of $G[S]$. I ...
1
vote
1answer
305 views

Strongly connected graph associated with a matrix

This type of matrices $L$ is called Leslie type matrices in Population dynamics: $$L = \begin{pmatrix} f_{11} & f_{12} & f_{13} & \dotsm & f_{1,i-1} & f_{1,i}& \dotsm & ...
1
vote
2answers
1k views

Do alternating and augmented paths for a matching need to cover all the edges in the matching?

Definition for alternating paths and augmented paths of a matching in a graph is defined as follows: Given a matching M, an alternating path is a path in which the edges belong alternatively to ...
1
vote
1answer
332 views

Is skew symmetry required for a flow network?

From Wikipedia: $G(V,E)$ is a finite directed graph in which every edge $\ (u,v) \in E$ has a non-negative, real-valued capacity $\ c(u,v)$. A flow network is a real function $\ f:V \times V ...
1
vote
1answer
212 views

Usage of Cauchy-Schwarz on graphs

Preface. I am reading up on the Chung-Graham-Wilson results on quasi-random graphs, and the description I'm reading is applying an apparently obvious usage of Cauchy-Schwarz that I'm just not seeing. ...
1
vote
1answer
37 views

If $G$ is a tree and $\forall v_1, v_2 : dist(v_1, v_2)$ is even, where $v_1, v_2-$ are leaves $\Rightarrow \exists!$ a maximal independent set.

If $G$ is a tree and $\forall v_1, v_2 : dist(v_1, v_2)$ is even, where $v_1, v_2-$ are leaves of the tree $\Rightarrow \exists!$ a maximal independent set. Give some clue please! Thanks anyway!
1
vote
1answer
293 views

Prove equivalence of conditions for a tree

Let $G=(V,E)$ denote a nonempty graph. Show that the following conditions are all equivalent. $G$ is a tree. Any two vertices in $G$ can be connected by a unique simple path. $G$ is ...
1
vote
2answers
92 views

Graph parameters that are equal for small graphs

Do you know of any pretty well known graph parameters which are equal for all small graphs (for $|G|$ small)? That is, there exist two parameters $a(G)$ and $b(G)$ such that $a(G) = b(G)$ for all ...
1
vote
2answers
110 views

Determining the equivalence of two statements

I have been given two statements and told that they are equivalent, but I'm having a hard time convincing myself of that. The two statements are: (1) "Every graph G has a minimum colouring in which ...
1
vote
1answer
535 views

How to prove the next properties for Critical graph?

This is a new question about Critical graph, because the previous question about it is became too big. Let me remind. In this context the Critical graph is: graph $G = (V, E)$ is Critical, if $G$ ...
1
vote
2answers
90 views

Acyclic graph (graph theory)

Let $v_1$, $v_2$, and $v_3$ be distinct vertices of a graph $G$ such that $G\setminus\{v_1\}$, $G\setminus\{v_2\}$ and $G\setminus\{v_3\}$ are all acyclic. Then prove that $G$ contains a maximum of ...
1
vote
1answer
2k views

Graph where all nodes are pivotal

I am reading a text for an upcoming class Social Network Analysis on Corsera.org and am trying to get a little bit ahead by reading some of the material before class starts. I am working on a question ...